DCEPC14G - God of Nim
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:
Game is played between 2 players, taking turns alternatively. Both play optimally.
There are N plies of coins, each containing exactly Pi coins.
There are N integers given. Let’s denote each of them by Ki.
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.
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.
Output exactly one string per test case, “Mishra” if Mishra wins the game or “Amit” if Amit wins the game.
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.
It seems that now i am the God Of Nim :p
good understanding of grundy numbers :)
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
I'm surprised when I see the optimal strategy for "general" nim game is very short to code :-O