分数: 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
这是游戏的一种可能的进展。
- 高桥写道 0 在广场上 6.
- 青木写道 1 在广场上 1.
- 高桥写道 1 在广场上 7.
那么,青木不能写 0 or 1 在任何方格上,所以高桥获胜。
示例输入 2
3 3 1 1 2 0 3 1
示例输出 2
Aoki
因为每个方格都已经有 0 or 1 开头写的是,先行的高桥无法行动,所以青木获胜。
示例输入 3
1000000000000000000 0
示例输出 3
Aoki