← 返回题目列表

Codeforces · 2171/C1

C1. Renako Amaori 和 XOR 游戏(简单版)

中文机器翻译题面 查看原题
是的。我不能再这样做了。不,该死的。方式。
— 雨织丽奈子

这是问题的简单版本。简单版本和困难版本之间的唯一区别是,在简单版本中,$$$a_i, b_i \leq 1$$$。

Renako 陷入进退两难的境地……当然,我指的是 Ajisai 和 Mai!两个人都想和她一起出去玩,她就是拿不定主意!因此,Ajisai 和 Mai 决定玩 XOR 游戏。

Ajisai 和 Mai 被赋予长度 $$$n$$$ 的数组 $$$a$$$ 和 $$$b$$$ ($$$0\leq a_i, b_i\leq {\color{red}{1}}$$$)。他们将玩一场持续 $$$n$$$ 回合的游戏,其中 Ajisai 在奇数回合中移动,Mai 在偶数回合中移动。在第 $$$i$$$ 回合,要移动的玩家可以选择交换 $$$a_i$$$ 和 $$$b_i$$$,或者放弃。

请注意,如果发生交换, 正在交换的索引必须与回合数匹配。例如,在第一回合,Ajisai 可以选择交换 $$$a_1$$$ 和 $$$b_1$$$,或者通过。在第二回合,Mai 可以选择交换 $$$a_2$$$ 和 $$$b_2$$$,或者通过。这将持续 $$$n$$$ 回合。因此,只有 Ajisai 可以交换奇数索引,只有 Mai 可以交换偶数索引。

游戏结束时,Ajisai 的得分为 $$$a_1 \oplus a_2 \oplus \dots \oplus a_n$$$,Mai 的得分为 $$$b_1 \oplus b_2 \oplus \dots \oplus b_n$$$$$$^{\text{*}}$$$。得分较高的玩家获胜。如果双方得分相同,则比赛以平局结束。

以最佳发挥确定游戏结果。更正式地说,如果存在一种策略,使一名玩家无论对手的选择如何总是获胜,则认为他以最佳发挥获胜。如果双方都没有这样的策略,则该游戏被视为具有最佳玩法的平局。

$$$^{\text{*}}$$$$$$\oplus$$$ 表示按位异或运算

输入

第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数,$$$a_1, a_2, \dots, a_n$$$ ($$$0\leq a_i\leq 1$$$)。

每个测试用例的第三行包含 $$$n$$$ 整数,$$$b_1, b_2, \dots, b_n$$$ ($$$0\leq b_i\leq 1$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,在单行上输出“紫菜斋“如果紫斋以最佳发挥获胜,”麦“如果Mai以最佳发挥获胜,或者”领带“如果比赛以最佳发挥平局结束。

您可以在任何情况下输出答案(上限或下限)。例如,字符串“毫安", "麦", "麦“,和”邮件“将被识别为”麦".

示例

输入
复制

6
4
1 0 0 1
1 0 1 1
6
0 1 1 1 1 0
0 0 1 0 1 1
4
0 0 1 0
1 0 1 1
5
1 0 1 1 1
0 1 1 1 0
6
1 1 1 1 1 1
1 1 1 1 1 1
5
0 1 0 0 1
1 0 0 1 1

输出
复制

Ajisai
Mai
Tie
Ajisai
Tie
Mai

注意

在第一个示例中,游戏可能的一种玩法如下:

在第 1 回合,Ajisai 选择交换 $$$a_1$$$ 和 $$$b_1$$$。现在数组是 $$$a = [1, 0, 0, 1]$$$ 和 $$$b = [1, 0, 1, 1]$$$。

在第2回合,Mai选择放弃。

在第 3 回合,Ajisai 选择交换 $$$a_3$$$ 和 $$$b_3$$$。现在数组是 $$$a = [1, 0, 1, 1]$$$ 和 $$$b = [1, 0, 0, 1]$$$。

在第 4 回合,Mai 选择交换 $$$a_4$$$ 和 $$$b_4$$$。现在数组是 $$$a = [1, 0, 1, 1]$$$ 和 $$$b = [1, 0, 0, 1]$$$。

现在,Ajisai 的最终得分为 $$$1\oplus 0\oplus 1\oplus 1 = 1$$$,Mai 的最终得分为 $$$1\oplus 0\oplus 0\oplus 1 = 0$$$。因此,阿吉斋赢得了比赛。

不保证上述描述代表最佳播放。