← 返回题目列表

Codeforces · 1365/A

A. 矩阵游戏

中文机器翻译题面 查看原题

Ashish 和 Vivek 在由 $$$n$$$ 行和 $$$m$$$ 列组成的矩阵上玩游戏,他们轮流声明单元格。无人认领的单元格由 $$$0$$$ 表示,而已认领的单元格由 $$$1$$$ 表示。给出了矩阵的初始状态。可能有一些处于初始状态的已声明单元格。

在每个回合中,玩家必须声明一个单元格。如果单元格无人认领并且不与任何其他已认领的单元格共享行或列,则可以认领该单元格。当玩家无法采取行动时,他就输了,游戏结束。

如果 Ashish 和 Vivek 轮流移动且 Ashish 先走,如果他们都发挥最佳,则确定游戏的获胜者。

两名玩家之间的最佳游戏意味着两名玩家都选择最佳策略来为自己实现最佳结果。

输入

第一行由一个整数 $$$t$$$ $$$(1 \le t \le 50)$$$ — 测试用例的数量组成。测试用例的描述如下。

每个测试用例的第一行由两个空格分隔的整数组成 $$$n$$$, $$$m$$$ $$$(1 \le n, m \le 50)$$$ - 矩阵中的行数和列数。

以下 $$$n$$$ 行每行包含 $$$m$$$ 个整数,$$$i$$$ 第 $$$i$$$ 行上的第 $$$j$$$ 整数表示 $$$a_{i,j}$$$ $$$(a_{i,j} \in \{0, 1\})$$$。

输出

对于每个测试用例,如果 Ashish 赢得游戏,则打印“Ashish”,否则打印“Vivek”(不带引号)。

示例

输入 #1

4
2 2
0 0
0 0
2 2
0 0
0 1
2 3
1 0 1
1 1 0
3 3
1 0 0
0 0 0
1 0 0

输出 #1

Vivek
Ashish
Vivek
Ashish

注意

对于第一种情况:一种可能的情况是:Ashish 声明单元格 $$$(1, 1)$$$,然后 Vivek 声明单元格 $$$(2, 2)$$$。 Ashish 既不能认领单元格 $$$(1, 2)$$$,也不能认领单元格 $$$(2, 1)$$$,因为单元格 $$$(1, 1)$$$ 和 $$$(2, 2)$$$ 已被认领。因此阿什什输了。可以证明,无论 Ashish 在这种情况下打什么,Vivek 都会赢。

对于第二种情况:Ashish 声明单元格 $$$(1, 1)$$$,这是唯一可以在第一步中声明的单元格。此后维韦克就没有任何动作了。

对于第三种情况:Ashish 无法移动,因此 Vivek 获胜。

对于第四种情况:如果 Ashish 声称单元格 $$$(2, 3)$$$,Vivek 将没有剩余的步数。