問題一覧 > 通常問題

No.2059 Odd Move Nim

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 97
作問者 : nok0nok0 / テスター : hir355hir355 ぷらぷら 👑 ygussanyygussany taiga0629kyoprotaiga0629kyopro
13 ProblemId : 7753 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-21 19:11:03

問題文

$1$ から $N$ の番号がついた石の山があります。最初、山 $i$ には $A_i$ 個の石があります。

これらを用いて、Alice と Bob がゲームをします。Alice から始めて、交互に次の操作を行い、操作を行えなくなった方が負けとなります。

  • $2$ 以上 $N$ 以下の整数 $i$ 、$1$ 以上 $i$ 未満の奇数 $x$ を選ぶ。 山 $i$ から $1$ 個以上の石を選んで、山 ${i-x}$ に移す。

二人が最適に行動したとき、どちらがゲームに勝つかを求めてください。

制約

  • 入力は全て整数である。
  • $2 \le N \le 200000$
  • $A_1 = 0$
  • $0 \le A_i< 2 ^ {30}\ (2\le i \le N)$

入力

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

出力

Alice が勝つ場合 Alice と、Bob が勝つ場合 Bob と出力せよ。

サンプル

サンプル1
入力
3
0 1 2
出力
Alice

はじめに山 $2$ の石を $1$ 個山 $1$ に動かすことで、 Alice は必ず勝利できます。

サンプル2
入力
4
0 1 0 1
出力
Bob

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