#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] 是奇数。
  • 所有输入值均为整数。