Add or Multiply Game

2 secs 1024 MB
askr_58's icon askr_58

問題文

黒板に NN 個の整数 A1,A2,......,ANA_1,A_2,......,A_N が、左からこの順に横一列に書かれています。 今からAliceとBobはこの整数列を使ってゲームをします。

Aliceが先攻で、次のような操作を交互に一回ずつ、黒板に書かれている整数がちょうど 11 個となるまで行います。

  • 黒板に書かれた整数列の中から、隣り合う二つの整数を一組選び削除する。その後同じ位置に、今消した二つの整数の和または積のうち好きなほうを一つ書き込む。

この操作により黒板に書かれている整数の個数がちょうど 11 つ減ることに注意してください。

全ての操作が終了した時点で、黒板に書かれている整数が奇数であればAliceの勝ちで、そうでなければBobの勝ちです。 両者が最善を尽くすとき、勝利するのはどちらですか?

制約

  • 2N2×1052\leq N\leq 2\times 10^5
  • 109Ai109-10^9\leq A_i\leq 10^9
  • 入力はすべて整数

入力

N
A_1 A_2 ...... A_N

出力

Aliceが勝つ場合 Aliceと、Bobが勝つ場合 Bobと出力してください。

サンプル

入力1
4
1 2 3 4  
出力1
Alice

ゲームの進行の一例として、以下のようなものが考えられます。

  • Aliceが隣り合う 3344 を削除し、その和である 77 を書き込む。黒板に書かれている整数列は 1,2,71,2,7 となる。
  • Bobが隣り合う 1122 を削除し、その和である 33 を書き込む。黒板に書かれている整数列は 3,73,7 となる。
  • Aliceが隣り合う 3377 を削除し、その積である 2121 を書き込む。黒板に書かれている整数列は 2121 となる。

この場合、全ての操作が終わった時点で黒板に書かれている整数は 2121 で奇数なので、Aliceの勝利です。 この入力では、Aliceが適切に操作を行うことで必ずAliceが勝利できることが証明できるので、Aliceと出力します。

入力2
15
3 -1 4 -1 5 -9 2 -6 5 -3 5 -8 9 -7 9
出力2
Bob

提出


Go (1.21)