← 返回题目列表

AtCoder · arc091_d

F. 奇怪的尼姆

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

分数: 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