問題一覧 > 通常問題

No.946 Box Box Box

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 61
作問者 : %20 / テスター : kotatsugame
お気に入りにしたユーザー ProblemId : 2684 / 自分の提出
問題文最終更新日: 2019-12-17 14:25:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2019 (順位表) の他の問題:

Problem Statement

$N$ unopened boxes are stacked in a single column, and the $i$-th box from the top contains $A_i$ balls.
The boxes are translucent, so the number of balls inside each box can be seen from the outside.

Takahashi and Takanashi decided to play a game using these boxes.
The rules of the game are as follows.

  • The players take turns performing one of the following operations.
    • Take down some consecutive boxes from the top of the stacked unopened boxes, and open all of the boxes taken down.
    • Choose $1$ opened box and take out some of the balls in that box.
  • The player who can no longer perform an operation loses. The player who performed the last operation wins.

Takahashi plays this game first. When both Takahashi and Takanashi act optimally, who will win?

Input

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

The input satisfies the following constraints.

  • $N,A_i$ are integers.
  • $1 \le N \le 2000$
  • $1 \le A_i \le 10^9$

Output

Print Takahashi if Takahashi wins, and Takanashi if Takanashi wins.

Sample

Sample 1
Input
3
1
3
5
Output
Takanashi

When both act optimally, Takanashi wins.

An example of play, not necessarily optimal, is as follows.

  • Takahashi takes down $1$ box and opens it. The numbers of balls in the opened boxes become $\{1\}$.
  • Takanashi takes out $1$ ball from the box containing $1$ ball. The numbers of balls in the opened boxes become $\{0\}$.
  • Takahashi takes down $2$ boxes and opens them. The numbers of balls in the opened boxes become $\{0,3,5\}$.
  • Takanashi takes out $4$ balls from the box containing $5$ balls. The numbers of balls in the opened boxes become $\{0,3,1\}$.
  • Takahashi takes out $1$ ball from the box containing $1$ ball. The numbers of balls in the opened boxes become $\{0,3,0\}$.
  • Takanashi takes out $3$ balls from the box containing $3$ balls. The numbers of balls in the opened boxes become $\{0,0,0\}$.
  • Takahashi cannot perform an operation, so he loses.
Sample 2
Input
4
3
7
2
6
Output
Takahashi

When both act optimally, Takahashi wins.

Sample 3
Input
10
1000000000
100000000
1
1000000
10
10000
100
100000
1000
10000000
Output
Takanashi

When both act optimally, Takanashi wins.

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