No.3718 XOR Escape
ぽえ
kazuppa
loop0919
問題文最終更新日: 2026-09-18 21:21:54
yukicoder contest 514
(順位表)
の他の問題:
問題文
正整数 $N$ と $A \oplus B \oplus C = 0$ を満たす正整数 $A, B, C$ が与えられる。
変数 $x$ があり、はじめ、$x = N$ である。
次の操作を好きな回数行えるとき、操作を行うことのできる回数の最大値を求めよ。
- $y \lt x$ と $x \oplus y \notin \{A, B, C\}$ の両方を満たす非負整数 $y$ を $1$ つ選び、変数 $x$ を $y$ に変更する。
ただし、 $\oplus$ はビット単位 $\mathrm{XOR}$ を表す。
ビット単位 $\mathrm{XOR}$ の定義（クリックで開く）
非負整数 $X, Y$ のビット単位 $\mathrm{XOR}$ すなわち $X \oplus Y$ は、以下のように定義される。- $X \oplus Y$ を二進表記したときの $2^k$ $(k \ge 0)$ の位の数は、 $X, Y$ を二進表記したときの $2^k$ $(k \ge 0)$ の位の数のうち一方のみが $1$ であれば $1$ 、そうでなければ $0$ である。
制約
- 入力はすべて整数である。
- $1 \le N, A, B, C \le 10^{18}$
- $A\oplus B\oplus C=0$
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A$ $B$ $C$
出力
答えを出力せよ。
サンプル
サンプル1
入力
10 1 2 3
出力
2
例えば、$x$ を $10\to7\to3$ と変更することで $2$ 回操作できる。
サンプル2
入力
20 10 13 7
出力
17
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。