103494: [Atcoder]ABC349 E - Weighted Tic-Tac-Toe

Problem Statement

There is a $3 \times 3$ grid. Let $(i, j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left $(1 \leq i, j \leq 3)$. Cell $(i, j)$ contains an integer $A_{i,j}$. It is guaranteed that $\sum_{i=1}^3 \sum_{j=1}^3 A_{i,j}$ is odd. Additionally, all cells are initially painted white.

Takahashi and Aoki will play a game using this grid. Takahashi goes first, and they take turns performing the following operation:

• Choose a cell $(i, j)$ $(1\leq i, j \leq 3)$ that is still painted white (it can be shown that such a cell always exists at the time of the operation). The player performing the operation scores $A_{i,j}$ points. Then, if the player is Takahashi, he paints the cell $(i, j)$ red; if the player is Aoki, he paints it blue.

After each operation, the following checks are made:

• Check if there are three consecutive cells painted the same color (red or blue) in any row, column, or diagonal. If such a sequence exists, the game ends immediately, and the player whose color forms the sequence wins.
• Check if there are white cells left. If no white cells remain, the game ends, and the player with the higher total score wins.

It can be shown that the game will always end after a finite number of moves, and either Takahashi or Aoki will win. Determine which player wins if both play optimally for victory.

Constraints

• $|A_{i,j}| \leq 10^9$
• $\sum_{i=1}^3 \sum_{j=1}^3 A_{i,j}$ is odd.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$A_{1,1}$ $A_{1,2}$ $A_{1,3}$
$A_{2,1}$ $A_{2,2}$ $A_{2,3}$
$A_{3,1}$ $A_{3,2}$ $A_{3,3}$

Output

If Takahashi wins, print Takahashi; if Aoki wins, print Aoki.

Sample Input 1

0 0 0
0 1 0
0 0 0

Sample Output 1

Takahashi

If Takahashi chooses cell $(2,2)$ in his first move, no matter how Aoki plays afterward, Takahashi can always act to prevent three consecutive blue cells. If three consecutive red cells are formed, Takahashi wins. If the game ends without three consecutive red cells, at that point, Takahashi has scored $1$ point and Aoki $0$ points, so Takahashi wins either way.

Sample Input 2

-1 1 0
-4 -2 -5
-4 -1 -5

Sample Output 2

Aoki

问题描述

有一个$3 \times 3$的网格。用$(i, j)$表示从顶部第$i$行，从左第$j$列的单元格 $(1 \leq i, j \leq 3)$。单元格$(i, j)$包含一个整数$A_{i,j}$。可以保证$\sum_{i=1}^3 \sum_{j=1}^3 A_{i,j}$是奇数。此外，所有单元格最初都是白色的。

Takahashi和Aoki将使用这个网格进行游戏。Takahashi先走，他们轮流执行以下操作：

• 选择一个仍然是白色的单元格$(i, j)$ $(1\leq i, j \leq 3)$（可以证明在操作时刻总是存在这样的单元格）。执行操作的玩家获得$A_{i,j}$分。然后，如果玩家是Takahashi，他将单元格$(i, j)$涂成红色；如果玩家是Aoki，他将其涂成蓝色。

每次操作后，进行以下检查：

• 检查是否存在任意一行、一列或对角线上连续的三个相同颜色（红色或蓝色）的单元格。如果存在这样的序列，游戏立即结束，形成该序列颜色的玩家获胜。
• 检查是否还有白色单元格。如果没有白色单元格剩下，游戏结束，总分较高的玩家获胜。

可以证明游戏总会在有限的回合后结束，要么Takahashi获胜，要么Aoki获胜。确定如果双方都为了胜利而最优地玩游戏，哪位玩家会获胜。

限制条件

• $|A_{i,j}| \leq 10^9$
• $\sum_{i=1}^3 \sum_{j=1}^3 A_{i,j}$是奇数。
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$A_{1,1}$ $A_{1,2}$ $A_{1,3}$
$A_{2,1}$ $A_{2,2}$ $A_{2,3}$
$A_{3,1}$ $A_{3,2}$ $A_{3,3}$

输出

如果Takahashi获胜，打印；如果Aoki获胜，打印。

样例输入1

0 0 0
0 1 0
0 0 0

样例输出1

Takahashi

如果Takahashi在他的第一回合选择单元格$(2,2)$，无论Aoki之后如何操作，Takahashi总能采取行动防止出现连续三个蓝色单元格。如果形成了连续的三个红色单元格，Takahashi获胜。如果游戏结束时没有连续的红色单元格，那时Takahashi得分为1分，Aoki得分为0分，所以无论哪种情况Takahashi都会获胜。

样例输入2

-1 1 0
-4 -2 -5
-4 -1 -5

样例输出2

Aoki