← 返回题目列表

AtCoder · arc151_c

C. 01 游戏

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 方格称为方格 1,方形 2, \ldots,方形 N,其中正方形 i 和正方形 i+1 与每个相邻 i = 1, 2, \ldots, N-1.

最初, M 的正方形有 上面写着 0 or 1 。 具体来说,对于每个 方格上写有 i = 1, 2, \ldots, M, Y_i 写在正方形上 X_i。 另一个 N-M 方块上没有任何文字。

高桥和青木将进行一场比赛。 两人将交替行动,高桥先行。

  • 选择一个还没有写任何内容的方格,然后写 0 or 1 在那个广场上。 这里,禁止使两个相邻的方格上写有相同的数字。

第一个无法行动的玩家失败;另一名玩家获胜。

当双方都采取最佳策略以取得胜利时,确定获胜者。

约束

  • 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}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

输出

如果高桥获胜,则打印 Takahashi;如果 Aoki 获胜,则打印 Aoki.


示例输入 1

7 2
2 0
4 1

示例输出 1

Takahashi

这是游戏的一种可能的进展。

  1. 高桥写道 0 在广场上 6.
  2. 青木写道 1 在广场上 1.
  3. 高桥写道 1 在广场上 7.

那么,青木不能写 0 or 1 在任何方格上,所以高桥获胜。


示例输入 2

3 3
1 1
2 0
3 1

示例输出 2

Aoki

因为每个方格都已经有 0 or 1 开头写的是,先行的高桥无法行动,所以青木获胜。


示例输入 3

1000000000000000000 0

示例输出 3

Aoki