DCEPC14G - God of Nim

## 题目描述 Amit与Mishra在玩游戏，游戏规则如下. ------------ 1. 两个玩家交替进行操作，两个人都玩得很好. 2. 有$N$堆硬币，每堆有$P_i$个. 3. 有$N$个整数，第$i$个整数是$K_i$. 4. 在一个回合中，轮到的玩家可以选择第i堆硬币并从中丢弃x个硬币（$1<=n<=K_i$）. 5. Amit总是先手，无法丢弃硬币的玩家即为输. ------------ 你能判断出Mishra是否赢了吗？ ## 输入输出格式 #### 输入格式 第一行是测试数据的组数$T$，每组测试数据中，第一行是$N$，第二行的$N$个整数表示硬币堆中的硬币数量，第三行的$N$个整数分别是$K_1$到$K_N$. #### 输出格式 输出T行。如果该组数据中Amit赢了就输出Amit，否则输出Mishra.

Amit is a big fan of Nim Game. Literally! He doesn’t just play the game, he fantasizes it. He follows the simple mantra – Eat, Sleep, Nim. His fantasy is overgrown over time that he has starting thinking of himself as God of Nim. Legend has that if you meet him, more often than not he is imagining a game played between you both and how he beats you with comfort. Frustrated with his never ending Nim fantasy, Mishra decides to give him a taste of his own medicine. Mishra devises a game which looks similar to Nim but is not in reality. Here’s how the game looks: 1. Game is played between 2 players, taking turns alternatively. Both play optimally. 2. There are N plies of coins, each containing exactly Pi coins. 3. There are N integers given. Let’s denote each of them by Ki. 4. In a single turn, a player can choose a pile Pi and can discard “x” coins from the pile Pi where 1<=x<=Ki. For example – if pile P1 is chosen by a player, then he can discard x coins such that 1<=x<=K1. 5. Amit always starts the game. The player who cannot make a move loses the game. If Mishra beats Amit in this game, Amit will have no option but to shed his Nim ego and so we all will be saved. Can you find out if Mishra succeeds?

First line contains T, the number of test cases. Each test cases starts with an integer N in first line. Next line consists of N integers, P1 to PN. Next line consists of N integers, K1 to KN. 1<=T<=10 1<=N<=10000 0<=Pi<=10^9 1<=Ki<=10^9

Output exactly one string per test case, “Mishra” if Mishra wins the game or “Amit” if Amit wins the game.

215224 71 3

AmitAmit Explanation:For second test case, one possible way of winning for Amit is – Amit and Mishra discard 1 coin alternatively from first pile, starting from Amit. Then Amit picks up 3 from second pile, Mishra picks up 1 from second pile and Amit finishes the game by picking up 3 coins left in the second pile.