分数: 900 点
问题陈述
高桥和青木正在玩取石子游戏。最初,有 N 成堆的石头,以及 i- 第堆包含 A_i 石头并且有一个关联的整数 K_i.
从高桥出发,高桥和青木轮流执行以下操作:
- 选择一堆。如果 i第-堆被选择并且有 X 石堆中剩下的石子,移走一些石子之间的石子 1 和 floor(X/K_i) (含)来自堆。
首先无法执行操作的玩家输掉游戏。假设双方都发挥最佳,确定游戏的获胜者。 在这里, floor(x) 表示不大于的最大整数 x.
约束
- 1 \leq N \leq 200
- 1 \leq A_i,K_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 K_1 : A_N K_N
输出
如果高桥获胜,则打印 Takahashi;如果 Aoki 获胜,则打印 Aoki.
样本输入 1
2 5 2 3 3
示例输出 1
Aoki
最初,最多从第一堆开始 floor(5/2)=2 石子可以一次移除,最多从第二堆中移除 floor(3/3)=1 石头可以一次移除。
- 如果高桥先从第一堆中取出两颗石子,则最多从第一堆中取出两颗石子 floor(3/2)=1 石头现在可以一次移除,并且最多从第二堆中移除 floor(3/3)=1 石头可以一次移除。
- 那么,如果青木从第二堆中取出一颗石子,则最多从第一堆中取出一颗石子 floor(3/2)=1 石头可以一次移除,并且从第二堆中不能再移除任何石头(因为 floor(2/3)=0).
- 那么,如果高桥从第一堆中取出一颗石子,则最多从第一堆中取出一颗石子 floor(2/2)=1 石头现在可以一次移除,并且从第二堆中不再可以移除石头。
- 那么,如果青木从第一堆中取出一颗石子,则最多从第一堆中取出一颗石子 floor(1/2)=0 石子现在可以一次移除,并且从第二堆中不再可以移除石子。
无法再执行任何操作,因此 Aoki 获胜。如果高桥打法不同,青木也可以相应地打法取胜。
示例输入 2
3 3 2 4 3 5 1
示例输出 2
Takahashi
示例输入 3
3 28 3 16 4 19 2
示例输出 3
Aoki
示例输入 4
4 3141 59 26535 897 93 23 8462 64
示例输出 4
Takahashi