2261C.md (2112B)
1 Source: https://codeforces.com/problemset/problem/2261/C 2 3 C. I Know About a Million Things 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 [月葬 - 黒魔 × rintaro soma](https://www.youtube.com/watch?v=4Mch-fZYQX8) 22 23 Moggity and Larpity are playing a game with an array $a_1, a_2, \ldots, a_n$ of positive integers. Moggity moves first, and then the players alternate turns. 24 25 On their turn, a player chooses a non-empty set of positions of the array and removes the elements at these positions. Such a move is allowed only if at least one of the following conditions holds: 26 27 * exactly one element is removed; 28 * the sum of the removed elements is even. 29 30 A player who cannot make a move loses. In other words, the player who faces an empty array loses. 31 32 Determine which player has a winning strategy. 33 34 Input 35 36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 37 38 The first line of each test case contains a single integer $n$ ($1 \le n \le 1\,000\,000$) — the length of the array. 39 40 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 1\,000\,000$) — the elements of the array. 41 42 It is guaranteed that the sum of $n$ over all test cases does not exceed $1\,000\,000$. 43 44 Output 45 46 For each test case, print "Moggity" if Moggity has a winning strategy, and "Larpity" otherwise. 47 48 You can output the answer in any case (upper or lower). For example, the strings "MoggItY", "MOGGITY", "moggity", and "mOGGity" will be recognized as a win for Moggity. 49 50 Example 51 52 Input 53 54 ``` 55 3 56 57 1 58 59 7 60 61 2 62 63 2 3 64 65 6 66 67 1000000 999999 5 4 3 2 68 ``` 69 70 Output 71 72 ``` 73 Moggity 74 75 Larpity 76 77 Moggity 78 ``` 79 80 Note 81 82 In the first test case, Moggity removes the only element, and Larpity faces an empty array. 83 84 In the second test case, Moggity cannot remove both elements at once, because $2 + 3 = 5$ is odd. Whichever single element he removes, Larpity removes the remaining one, and then Moggity faces an empty array. Therefore, Larpity wins.