問題一覧 > 通常問題

No.946 箱箱箱

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 56
作問者 : %20%20 / テスター : kotatsugamekotatsugame
24 ProblemId : 2684 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-12-17 14:25:50

問題文

$N$ 個の未開封の箱が一列に積み重なっていて、上から $i$ 番目の箱には $A_i$ 個のボールが入っています。
箱は半透明なので中に入っているボールの個数は外から把握できます。

高橋さんと小鳥遊さんはこの箱を使ってゲームをすることにしました。
ゲームのルールは以下の通りです。

  • 各プレイヤーは交互に次のどちらかの操作をします。
    • 積み重なっている未開封の箱のうち上から連続するいくつかの箱を降ろし、降ろした箱全てを開封する。
    • 開封済みの箱を $1$ つ選び、その箱に入っているいくつかのボールを取り出す。
  • 操作できなくなった方が負けです。最後に操作した方が勝ちです。

高橋さんが先手でこのゲームをし、高橋さんと小鳥遊さんがともに最適な行動をしたとき、どちらが勝つでしょうか？

入力

$N$
$A_1$
$A_2$
$\vdots$
$A_N$

入力は以下の制約を満たします。

  • $N,A_i$ は整数である。
  • $1 \le N \le 2000$
  • $1 \le A_i \le 10^9$

出力

高橋さんが勝つならTakahashiを、小鳥遊さんが勝つならTakanashiを出力してください。

サンプル

サンプル1
入力
3
1
3
5
出力
Takanashi

最適に行動したとき、小鳥遊さんが勝ちます。

最適とは限らない行動例は以下のようになります。

  • 高橋さんが、箱を $1$ 個降ろして開封する。開封済みの箱に入っているボールの個数は $\{1\}$ になる。
  • 小鳥遊さんが、ボールが $1$ 個入っている箱からボールを $1$ 個取り出す。開封済みの箱に入っているボールの個数は $\{0\}$ になる。
  • 高橋さんが、箱を $2$ 個降ろして開封する。開封済みの箱に入っているボールの個数は $\{0,3,5\}$ になる。
  • 小鳥遊さんが、ボールが $5$ 個入っている箱からボールを $4$ 個取り出す。開封済みの箱に入っているボールの個数は $\{0,3,1\}$ になる。
  • 高橋さんが、ボールが $1$ 個入っている箱からボールを $1$ 個取り出す。開封済みの箱に入っているボールの個数は $\{0,3,0\}$ になる。
  • 小鳥遊さんが、ボールが $3$ 個入っている箱からボールを $3$ 個取り出す。開封済みの箱に入っているボールの個数は $\{0,0,0\}$ になる。
  • 高橋さんが、操作できないので負ける。
サンプル2
入力
4
3
7
2
6
出力
Takahashi

最適に行動したとき、高橋さんが勝ちます。

サンプル3
入力
10
1000000000
100000000
1
1000000
10
10000
100
100000
1000
10000000
出力
Takanashi

最適に行動したとき、小鳥遊さんが勝ちます。

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