AT_abc349_e [ABC349E] Weighted Tic-Tac-Toe

题目描述

有一个 $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}$ 是奇数。所有格子初始时都是白色。

高桥君和青木君用这个格子进行游戏。游戏中，高桥君先手，两人轮流进行如下操作：

• 选择一个当前为白色的格子 $(i, j)$（保证每次操作时一定存在这样的格子）。进行操作的玩家获得 $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

输入 #1

0 0 0
0 1 0
0 0 0

输出 #1

Takahashi

输入输出样例 #2

输入 #2

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

输出 #2

Aoki

说明/提示

限制条件

• $|A_{i, j}| \leq 10^9$
• $\sum_{i=1}^3 \sum_{j=1}^3 A_{i, j}$ 为奇数
• 输入均为整数

样例解释 1

如果高桥君第一步选择 $(2, 2)$，无论青木君如何行动，高桥君都可以通过合理操作避免出现三连蓝。如果出现三连红，则高桥君获胜。如果没有出现三连红且游戏结束，此时高桥君得 $1$ 分，青木君得 $0$ 分，因此无论如何高桥君都能获胜。

由 ChatGPT 4.1 翻译