/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 900 点
問題文
高橋君と青木君は、石取りゲームをしています。最初、山が N 個あり、i 個目の山には A_i 個の石があり、整数 K_i が定まっています。
高橋君と青木君は、高橋君から始めて、交互に以下の操作を繰り返します。
- 山を 1 つ選ぶ。i 個目の山を選び、その山に X 個の石が残っている場合、1 個以上 floor(X/K_i) 個以下の任意の個数の石を 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 を出力せよ。
入力例 1
2 5 2 3 3
出力例 1
Aoki
最初、1 個目の山からは floor(5/2)=2 個まで、2 個目の山からは floor(3/3)=1 個までの石を一度に取り除くことができます。
- 高橋君が最初に 1 個目の山から 2 個の石を取ると、1 個目の山からは floor(3/2)=1 個まで、2 個目の山からは floor(3/3)=1 個までの石を一度に取り除くことができるようになります。
- 次に、青木君が 2 個目の山から 1 個の石を取ると、1 個目の山からは floor(3/2)=1 個までの石を取り除くことができ、2 個目の山からは (floor(2/3)=0 より) 石を取り除くことができなくなります。
- 次に、高橋君が 1 個目の山から 1 個の石を取ると、1 個目の山からは floor(2/2)=1 個までの石を一度に取り除くことができるようになります。2 個目の山からは石を取り除くことはできません。
- 次に、青木君が 1 個目の山から 1 個の石を取ると、1 個目の山からは floor(1/2)=0 個までの石を一度に取り除くことができるようになります。2 個目の山からは石を取り除くことはできません。
これ以上の操作はできないため、青木君の勝ちです。高橋君がそれ以外の行動をした場合も、青木君はうまく行動を選ぶことで勝つことができます。
入力例 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
Score : 900 points
Problem Statement
Takahashi and Aoki are playing a stone-taking game. Initially, there are N piles of stones, and the i-th pile contains A_i stones and has an associated integer K_i.
Starting from Takahashi, Takahashi and Aoki take alternate turns to perform the following operation:
- Choose a pile. If the i-th pile is selected and there are X stones left in the pile, remove some number of stones between 1 and floor(X/K_i) (inclusive) from the pile.
The player who first becomes unable to perform the operation loses the game. Assuming that both players play optimally, determine the winner of the game. Here, floor(x) represents the largest integer not greater than x.
Constraints
- 1 \leq N \leq 200
- 1 \leq A_i,K_i \leq 10^9
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N A_1 K_1 : A_N K_N
Output
If Takahashi will win, print Takahashi; if Aoki will win, print Aoki.
Sample Input 1
2 5 2 3 3
Sample Output 1
Aoki
Initially, from the first pile at most floor(5/2)=2 stones can be removed at a time, and from the second pile at most floor(3/3)=1 stone can be removed at a time.
- If Takahashi first takes two stones from the first pile, from the first pile at most floor(3/2)=1 stone can now be removed at a time, and from the second pile at most floor(3/3)=1 stone can be removed at a time.
- Then, if Aoki takes one stone from the second pile, from the first pile at most floor(3/2)=1 stone can be removed at a time, and from the second pile no more stones can be removed (since floor(2/3)=0).
- Then, if Takahashi takes one stone from the first pile, from the first pile at most floor(2/2)=1 stone can now be removed at a time, and from the second pile no more stones can be removed.
- Then, if Aoki takes one stone from the first pile, from the first pile at most floor(1/2)=0 stones can now be removed at a time, and from the second pile no more stones can be removed.
No more operation can be performed, thus Aoki wins. If Takahashi plays differently, Aoki can also win by play accordingly.
Sample Input 2
3 3 2 4 3 5 1
Sample Output 2
Takahashi
Sample Input 3
3 28 3 16 4 19 2
Sample Output 3
Aoki
Sample Input 4
4 3141 59 26535 897 93 23 8462 64
Sample Output 4
Takahashi