#10949. E - Weighted Tic-Tac-Toe 加权井字棋 比赛编号349
E - Weighted Tic-Tac-Toe 加权井字棋 比赛编号349
时间限制:2秒 / 内存限制:1024 MB
分数:450分
问题描述
有一个 3×3 的网格。令 (i,j) 表示第 i 行、第 j 列的格子(1≤i,j≤3)。每个格子 (i,j) 都包含一个整数 **A[i,j]**。保证所有格子的值之和是奇数。此外,所有格子初始时都是白色的。
Takahashi 和 Aoki 将在这个网格上进行游戏。Takahashi 先手,他们轮流进行以下操作:
- 选择一个仍然是白色的格子 **(i,j)**(在每次操作时,总能找到一个白色的格子)。执行该操作的玩家将获得 A[i,j] 分。如果是 Takahashi 执行操作,他将该格子涂成红色;如果是 Aoki 执行操作,他将该格子涂成蓝色。
- 每次操作后,进行如下检查:
- 检查是否有连续三个格子被同色(红色或蓝色)涂色,这三个格子必须在同一行、同一列或对角线上。如果存在这样的连续三个格子,游戏立即结束,涂成该颜色的玩家获胜。
- 检查是否还有白色格子。如果没有白色格子,游戏结束,分数更高的玩家获胜。
可以证明,游戏会在有限的步数后结束,且最终会有一个玩家获胜。假设两名玩家都能做到最佳策略,判断哪一位玩家会获胜。
输入格式
输入数据通过标准输入给出,格式如下:
A1,1 A1,2 A1,3
A2,1 A2,2 A2,3
A3,1 A3,2 A3,3
其中 A[i,j] 是第 i 行、第 j 列的格子上的整数。
输出格式
如果 Takahashi 获胜,输出 Takahashi
;如果 Aoki 获胜,输出 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
约束条件
- |A[i,j]| ≤ 10^9
- ∑ i=1 3 ∑ j=1 3 A[i,j] 是奇数。
- 所有输入值均为整数。