No.2538 2進元ゲーム
タグ : / 解いたユーザー数 28
作問者 : 👑
p-adic
/ テスター :
ecottea
hiro1729
問題文
まずは記法と用語を導入します。整数列 $a$ とその長さ以下の各正整数 $i$ に対し、$a_i$ で $a$ の $i$ 個目の成分を表します。
各非負整数 $m$ と整数 $n$ に対し、$n$ の $2$ 進展開における $2^m$ の位とは、
- $n \geq 0$ の時は $n$ の $2$ 進法表記における $2^m$ の位
- $n < 0$ の時は $-n$ を $\max \{m+1,-n\}$ 桁の $2$ 進法表記で表した時の $2$ の補数すなわち $2^{\max \{m+1,-n\}}+n$ の、$2$ 進法表記における $2^m$ の位
を表します。
整数の $2$ 進法表記を知らない人向けの説明はこちらです。（クリックで開く）
$n$ の $2$ 進展開における $2^m$ の位とは、以下の $2$ 条件を全て満たす一意な整数 $d$ のことです：
- $d$ は $0$ または $1$ である。
- $n = q 2^{m+1} + d2^m + r$ かつ $0 \leq r < 2^m$ を満たす整数 $q, r$ が存在する。
まず例えば $n = 0$ とします。$n$ の $2$ 進展開における $2^m$ の位は $m$ によらず $\textcolor{red}{0}$ です。実際 $d = \textcolor{red}{0}$ は条件1を満たし、条件2において $(q,r) = (0,0)$ と選ぶことができます。
次に例えば $n = 2$ とします。$m = 1$ の時、$n$ の $2$ 進展開における $2^m$ の位は $\textcolor{red}{1}$ です。実際 $d = \textcolor{red}{1}$ は条件1を満たし、条件2において $(q,r) = (0,0)$ と選ぶことができます。一方で $m \neq 1$ の時、$n$ の $2$ 進展開における $2^m$ の位は $\textcolor{red}{0}$ です。実際、$d = \textcolor{red}{0}$ は条件1を満たし、条件2において $m = 0$ ならば $(q,r) = (2^{-(m+1)}n,0)$ と選べ、$m > 1$ ならば $(q,r) = (0,2)$ と選べます。
最後に例えば $n = -1$ とします。この時、$n$ の $2$ 進展開における $2^m$ の位は $\textcolor{red}{1}$ です。実際 $d = \textcolor{red}{1}$ は条件1を満たし、条件2において $(q,r) = (-1,2^m-1)$ と選べます。
なお $n$ を整数より広く $2$ 進整数に拡張して考えることもあり、この時は $q$ の動く範囲も $2$ 進整数に広げて考えます。
各非負整数 $m$ と整数 $n$ に対し、$m$ が $n$ の $2$ 進元であるとは、$n$ の $2$ 進展開における $2^m$ の位が $1$ であるということです：
$2$ 進元の例はこちらです。（クリックで開く）
まず例えば $n = 0$ とします。この時、$m$ は $n$ の $2$ 進元になりえません。
次に例えば $n = 2$ とします。$m$ が $n$ の $2$ 進元である必要十分条件は、$m = 1$ です。
最後に例えば $n = -1$ とします。この時、常に $m$ は $n$ の $2$ 進元です。
入力に正整数 $N$ と長さ $N$ の整数列 $A$ が与えられます。
$2$ 進元大好きbotは $2$ 進元が大好きなbotです。
$2$ 進元大好きbot大好きbotは $2$ 進元大好きbotが大好きなbotです。もちろん２体は別物です。
$2$ 進元大好きbotと $2$ 進元大好きbot大好きbotの２体をプレイヤーとする「初期値 $A$ の $2$ 進元ゲーム」を次のように定義します：
- まず整数列 $a$ を $A$ と定める。
- 次に２体のプレイヤーは $2$ 進元大好きbotから始めて交互に次の操作を行える限り行う：
- $N$ 以下の正整数 $i$ と $a_i$ の値の $2$ 進元である非負整数 $m$ を $1$ つ選び、$a_i$ の値を $m$ に置き換えることで $a$ を更新する。
- 上記の操作が行えなくなった時、操作を行えなかったプレイヤーの敗北となり、すなわちもう片方のプレイヤーの勝利となる。
初期値 $A$ の $2$ 進元ゲームにおいて２体が自分の勝利を目指し相手の勝利を避けるように最善の手順を選んだ時、有限回の操作で勝敗がつくか否かと、勝敗がつく場合にどちらが勝利するかを求めてください。
入力
入力は以下の形式で標準入力から $2$ 行で与えられます：
- $1$ 行目に $N$ が与えられます。
- $2$ 行目に $A$ の各成分が半角空白区切りで与えられます。
$N$ $A_1$ $\cdots$ $A_N$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^5$ を満たす整数である。
- $N$ 以下の任意の正整数 $i$ に対し、$A_i$ は $-10^{18} \leq A_i \leq 10^{18}$ を満たす整数である。
出力
以下の形式で $1$ 行で出力してください：
- 有限回の操作で勝敗がつかないならば
0と出力してください。 - $2$ 進元大好きbotが勝利するならば
1と出力してください。 - $2$ 進元大好きbot大好きbotが勝利するならば
2と出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 0
出力
2
最初に長さ $N = 1$ の整数列 $a$ が $A = (0)$ として与えられます。$N$ 以下の正整数 $i$ は $1$ に限られるので $i$ の選択は省略して説明します。
$a_1 = 0$ は $2$ 進元を持たないので先攻の $2$ 進元大好きbotは操作できません。従って後攻の $2$ 進元大好きbot大好きbotの必勝となります。
サンプル2
入力
1 1
出力
1
最初に長さ $N = 1$ の整数列 $a$ が $A = (1)$ として与えられます。$N$ 以下の正整数 $i$ は $1$ に限られるので $i$ の選択は省略して説明します。
まず先攻の $2$ 進元大好きbotは $a_1 = 1$ の $2$ 進元である非負整数 $0$ を選び $a_1$ を $0$ に置き換えることができます。これにて $a$ が $(0)$ に更新されました。
すると $a_1 = 0$ は $2$ 進元を持たないので後攻の $2$ 進元大好きbot大好きbotは操作を行えません。従って $2$ 進元大好きbotの必勝となります。
サンプル3
入力
1 2
出力
2
最初に長さ $N = 1$ の整数列 $a$ が $A = (2)$ として与えられます。$N$ 以下の正整数 $i$ は $1$ に限られるので $i$ の選択は省略して説明します。
まず $2$ の $2$ 進元である非負整数は $1$ に限られるので、先攻の $2$ 進元大好きbotは $1$ を選び $a_1$ を $1$ に置き換えるしかありません。これにて $a$ が $(1)$ に更新されました。
後攻の $2$ 進元大好きbot大好きbotは $a_1 = 1$ の $2$ 進元である非負整数 $0$ を選び $a_1$ を $0$ に置き換えることができます。これにて $a$ が $(0)$ に更新されました。
すると $a_1 = 0$ は $2$ 進元を持たないので $2$ 進元大好きbotはそれ以上操作を行えません。従って $2$ 進元大好きbot大好きbotの必勝となります。
サンプル4
入力
1 -1
このように $A$ の成分に負の整数が現れることがあります。
出力
1
最初に長さ $N = 1$ の整数列 $a$ が $A = (-1)$ として与えられます。$N$ 以下の正整数 $i$ は $1$ に限られるので $i$ の選択は省略して説明します。
まず先攻の $2$ 進元大好きbotは $a_1 = -1$ の $2$ 進元である非負整数 $0$ を選び $a_1$ を $0$ に置き換えることができます。これにて $a$ が $(0)$ に更新されました。
すると $a_1 = 0$ は $2$ 進元を持たないので後攻の $2$ 進元大好きbot大好きbotは操作を行えません。従って $2$ 進元大好きbotの必勝となります。
サンプル5
入力
2 1 1
出力
2
最初に長さ $N = 2$ の整数列 $a$ が $A = (1,1)$ として与えられます。$N$ 以下の正整数 $i$ は $1,2$ の $2$ つがあります。
まず先攻の $2$ 進元大好きbotは $i$ を $1$ か $2$ のいずれかから選びます。
まず $2$ 進元大好きbotが最初に $i = 1$ と選んだ場合を考えます。$a_1 = 1$ の $2$ 進元は $0$ しかありませんので $2$ 進元大好きbotは $0$ を選び $a_1$ を $0$ に置き換えるしかありません。これにて $a$ が $(0,1)$ に更新されました。
後攻の $2$ 進元大好きbot大好きbotは $i = 2$ と $a_2 = 1$ の $2$ 進元 $0$ を選び $a_2$ を $0$ に置き換えることができます。これにて $a$ が $(0,0)$ に更新されました。
すると $2$ 進元大好きbotは $i$ を $1,2$ のどちらと選んでも $a_i = 0$ であり、$0$ は $2$ 進元を持たないため操作を行えません。従ってこの場合は $2$ 進元大好きbot大好きbotの勝利となります。
次に $2$ 進元大好きbotが最初に $i = 2$ と選んだ場合を考えます。$a_2 = 1$ の $2$ 進元は $0$ しかありませんので $2$ 進元大好きbotは $0$ を選び $a_2$ を $0$ に置き換えるしかありません。これにて $a$ が $(1,0)$ に更新されました。
後攻の $2$ 進元大好きbot大好きbotは $i = 1$ と $a_1 = 1$ の $2$ 進元 $0$ を選び $a_1$ を $0$ に置き換えることができます。これにて $a$ が $(0,0)$ に更新されました。
すると $2$ 進元大好きbotは $i$ を $1,2$ のどちらと選んでも $a_i = 0$ であり、$0$ は $2$ 進元を持たないため操作を行えません。従ってこの場合も $2$ 進元大好きbot大好きbotの勝利となります。
以上より、$2$ 進元大好きbot大好きbotの必勝となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。