codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.