201512: [AtCoder]ARC151 C - 01 Game

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

There are $N$ squares called square $1$, square $2$, $\ldots$, square $N$, where square $i$ and square $i+1$ are adjacent for each $i = 1, 2, \ldots, N-1$.

Initially, $M$ of the squares have $0$ or $1$ written on them. Specifically, for each $i = 1, 2, \ldots, M$, $Y_i$ is written on square $X_i$. The other $N-M$ squares have nothing written on them.

Takahashi and Aoki will play a game against each other. The two will alternately act as follows, with Takahashi going first.

  • Choose a square with nothing written yet, and write $0$ or $1$ on that square. Here, it is forbidden to make two adjacent squares have the same digit written on them.

The first player to be unable to act loses; the other player wins.

Determine the winner when both players adopt the optimal strategy for their own victory.

Constraints

  • $1 \leq N \leq 10^{18}$
  • $0 \leq M \leq \min\lbrace N, 2 \times 10^5 \rbrace$
  • $1 \leq X_1 \lt X_2 \lt \cdots \lt X_M \leq N$
  • $Y_i \in \lbrace 0, 1\rbrace$
  • $X_i + 1 = X_{i+1} \implies Y_i \neq Y_{i+1}$
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_M$ $Y_M$

Output

If Takahashi wins, print Takahashi; if Aoki wins, print Aoki.


Sample Input 1

7 2
2 0
4 1

Sample Output 1

Takahashi

Here is one possible progression of the game.

  1. Takahashi writes $0$ on square $6$.
  2. Aoki writes $1$ on square $1$.
  3. Takahashi writes $1$ on square $7$.

Then, Aoki cannot write $0$ or $1$ on any square, so Takahashi wins.


Sample Input 2

3 3
1 1
2 0
3 1

Sample Output 2

Aoki

Since every square already has $0$ or $1$ written at the beginning, Takahashi, who goes first, cannot act, so Aoki wins.


Sample Input 3

1000000000000000000 0

Sample Output 3

Aoki

Input

题意翻译

Takahashi 和 Aoki 在一个长为 $N$ 的数轴上做游戏。初始时,有 $M$ 个点有颜色,$X_i$ 位置上有颜色为 $Y_i$ 的点。Takahashi 先手,两人轮流操作,操作的内容是在数轴上没有点的位置上放置一点,需要满足其颜色与相邻两点(如果不为空)的颜色不同。若轮到一人操作时,无法再进行操作,则另一人获胜,游戏结束。给出游戏初始局面(保证合法),问谁有必胜策略。 $N\le 10^{18},M\le\min(N,2\times10^5)$

加入题单

上一题 下一题 算法标签: