No.3046 White Tiger vs Monster
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 2
作問者 :
Naru820
/ テスター :
okkuukenken
タグ : / 解いたユーザー数 2
作問者 :
問題文最終更新日: 2025-03-22 21:04:48
問題文
ホワイトタイガーは$N$体のモンスターと戦っています。
$i$番目のモンスターの体力は$A_i$です。また、初めのホワイトタイガーの攻撃力は$B$です。
ホワイトタイガーは、現在の攻撃力が、モンスターの体力以上である時かつその時に限り、モンスターに攻撃することができます。
また、モンスターに攻撃を行うと、そのモンスターは消滅し、さらに、攻撃を行う前のホワイトタイガーの攻撃力を$X$、攻撃されたモンスターの体力を$Y$としたとき、ホワイトタイガーの攻撃力が$X \oplus Y$に変化します。
ここで、$\oplus$はビットごとの排他的論理和を表します。
ホワイトタイガーが上手くモンスターに攻撃する順序を決めたとき、最大で何体モンスターを倒せるでしょうか?
制約
- $1 \leq N \leq 2\times 10^5$
- $1 \leq B \leq 10^{18}$
- $1 \leq A_i \leq 10^{18}$
入力
入力は以下の形式で標準入力から与えられる。
$N\ B$ $A_1\ A_2 \ldots \ A_N$
出力
1行に、ホワイトタイガーが倒せるモンスターの最大値を出力せよ。
サンプル
サンプル1
入力
3 5 1 3 5
出力
3
ホワイトタイガーは、以下のようにすれば、3体全てのモンスターを倒すことができます。
- モンスター2を倒す。ホワイトタイガーの攻撃力が $5 \oplus3 = 6$になる。
- モンスター3を倒す。ホワイトタイガーの攻撃力が $6 \oplus 5 = 3$になる。
- モンスター1を倒す。ホワイトタイガーの攻撃力が $3 \oplus 1 = 2$になる。
よって、答えは $3$ です。
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。