問題一覧 > 通常問題

No.3046 White Tiger vs Monster

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 2
作問者 : Naru820 / テスター : okkuukenken
0 ProblemId : 12116 / 自分の提出
問題文最終更新日: 2025-03-22 21:04:48

問題文

ホワイトタイガーはNN体のモンスターと戦っています。

ii番目のモンスターの体力はAiA_iです。また、初めのホワイトタイガーの攻撃力はBBです。

ホワイトタイガーは、現在の攻撃力が、モンスターの体力以上である時かつその時に限り、モンスターに攻撃することができます。

また、モンスターに攻撃を行うと、そのモンスターは消滅し、さらに、攻撃を行う前のホワイトタイガーの攻撃力をXX、攻撃されたモンスターの体力をYYとしたとき、ホワイトタイガーの攻撃力がX⊕YX \oplus Yに変化します。

ここで、⊕\oplusはビットごとの排他的論理和を表します。

ホワイトタイガーが上手くモンスターに攻撃する順序を決めたとき、最大で何体モンスターを倒せるでしょうか？

制約

  • 1≤N≤2×1051 \leq N \leq 2\times 10^5
  • 1≤B≤10181 \leq B \leq 10^{18}
  • 1≤Ai≤10181 \leq A_i \leq 10^{18}

入力

入力は以下の形式で標準入力から与えられる。

N BN\ B
A1 A2… ANA_1\ A_2 \ldots \ A_N

出力

1行に、ホワイトタイガーが倒せるモンスターの最大値を出力せよ。

サンプル

サンプル1
入力
3 5
1 3 5
出力
3

ホワイトタイガーは、以下のようにすれば、3体全てのモンスターを倒すことができます。

  • モンスター2を倒す。ホワイトタイガーの攻撃力が 5⊕3=65 \oplus3 = 6になる。
  • モンスター3を倒す。ホワイトタイガーの攻撃力が 6⊕5=36 \oplus 5 = 3になる。
  • モンスター1を倒す。ホワイトタイガーの攻撃力が 3⊕1=23 \oplus 1 = 2になる。

よって、答えは 33 です。

サンプル2
入力
2 1
1 2
出力
1
サンプル3
入力
15 49497
1964 616 419 161 9 2 6 19 49 49 4619649 16 19 16961 9619
出力
14

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。