P3339 [ZJOI2014] Take-Stones Game

Roland P. Sprague and Patrick M. Grundy are both passionate enthusiasts of combinatorial games, but they have never met. One day, in a letter to Grundy, Sprague introduced a supposedly ancient game from the East — Take-Stones. Take-Stones is a two-player impartial game. At the beginning of the game, there are several piles of stones on the table. Then the players take turns: choose one pile and remove any positive number of stones from that pile (but you must take at least one). The player who cannot make a move loses, and the other player wins. Due to practical constraints, Sprague suggested writing a row of natural numbers on paper to represent the sizes of the piles, and then the two would take turns crossing out and writing numbers; Grundy gladly agreed. A month passed, and after Grundy had lost $5$ games in a row, he suspected that Sprague was cheating. After several days of study, one afternoon Grundy discovered that if both players are clever enough, then given an initial position (a row of natural numbers), there is a very simple way to determine whether the first player or the second player has a forced win, and even to provide a winning strategy! So Grundy decided to strike back. The next day, in a letter to Sprague, Grundy suggested making the rules a bit more complicated: first fix a constant $K$. Then each move is changed to: choose a number and cross it out. Suppose the chosen number is $x$. The player may choose any positive integer a; after crossing out $x$, they must write down $x-a$，$x-2a $，$\cdots$，$x-K \times a$ — a total of $K$ numbers — and $a$ must satisfy $x-K\times a \geq 0$. If no such a exists, then the player cannot cross out this number. A player still loses if and only if they have no legal move. For the sake of pride, Sprague could not refuse. But he would not sit and wait for defeat either. He has already obtained the numbers written on the paper. He tells you this testdata and the rules of the game — you, a computer scientist studying how to use a not-yet-existing machine (which you name a “computer”) to solve practical problems in mathematics, physics, and economics.

In the input file, the first line is a positive integer representing the number of test cases $T$ (the number of times Sprague consults you). Then $T$ test cases follow, each occupying $N + 2$ lines, in the following format: - Line $1$: an empty line. - Line $2$: two positive integers, in order, representing $N$ and $K$. - The next $N$ lines: each line contains one positive integer, representing the $N$ numbers written on the paper.

The output file contains $T$ lines. For each test case, if the first player (the player who moves first) has a winning strategy, print `Preempt.`. If the second player has a winning strategy, print `Leapfrog.`. If neither of the above applies, print `Je suis un imbecile.`.

$10\%$ of the testdata satisfies: $N \leq 5$, $K=1$, and all numbers are at most $5$. $20\%$ of the testdata satisfies: $N \leq 100$, $K=1$, and all numbers are at most $10^9$. $10\%$ of the testdata satisfies: $N \leq 100$, $K=2$, and all numbers are at most $10^9$. $20\%$ of the testdata satisfies: $N \leq 100$, $K=2$, and all numbers are at most $10^{18}$. $20\%$ of the testdata satisfies: $N \leq 100$, $K=10$, and all numbers are at most $10^{18}$. $40\%$ of the testdata satisfies: $N \leq 100$, $K=30$, and all numbers are at most $10^{80}$. $100\%$ of the testdata satisfies: $T \leq 10$. Translated by ChatGPT 5