| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 101 | 42 | 35 | 42.169% |
Bessie and Elsie are playing a game of Moorbles. The game works as follows: Bessie and Elsie each start out with some amount of marbles. Bessie holds out $A$ of her marbles in her hoof and Elsie guesses if $A$ is Even or Odd. If Elsie is correct, she wins the $A$ marbles from Bessie and if she guesses incorrectly, she loses $A$ of her marbles to Bessie (if Elsie has less than $A$ marbles, she loses all her marbles). A player loses when they lose all of their marbles.
After some amount of turns in the game, Elsie has $N$ $(1 \leq N \leq 10^9)$ marbles. She thinks it is hard to win, but she is playing to not lose. After being around Bessie enough, Elsie has a good read on Bessie's habits and recognizes that on turn $i,ドル there are only $K$ $(1 \leq K \leq 4)$ different amounts of marbles that Bessie may put out. There are only $M$ $(1 \leq M \leq 3 \cdot 10^5)$ turns before Bessie gets bored and stops playing. Can you identify a lexicographically minimum turn sequence such that Elsie will not lose, regardless of how Bessie plays?
The first line contains a single integer $T$ (1ドル \leq T \leq 10$) representing the number of test cases. Each test case is described as follows:
It is guaranteed that the sum of $M$ over all test cases is at most 3ドル \cdot 10^5$.
For each test case, output the lexicographically minimum move sequence for Elsie to guarantee not losing, or $-1$ if she will lose. The move sequence should be on a single line and consist of $M$ space-separated tokens each equal to either "Even" or "Odd".
Note: "Even" is lexicographically smaller than "Odd".
2 10 3 2 2 5 1 3 1 3 10 3 3 2 7 5 8 3 4 2 5 6
Even Even Odd -1
In the first case, the only lexicographically smaller sequence of moves is "Even Even Even", but Bessie can make Elsie lose in that case by first playing 5ドル,ドル which reduces Elsie's number of marbles from 10ドル$ to 5ドル,ドル then playing 3ドル,ドル which reduces Elsie's number of marbles from 5ドル$ to 2ドル,ドル then playing 3ドル,ドル which wipes out all of her marbles.
If Elsie instead plays the correct move sequence "Even Even Odd", then if Bessie plays the same way, at the end when she plays 3ドル,ドル Elsie will gain those 3ドル$ marbles, increasing her number of marbles to 5ドル$. It can further be shown that Bessie cannot play in a different way to take all of Elsie's marbles given that Elsie plays "Even Even Odd".
In the second case, it can be shown that for any move sequence that Elsie could choose, Bessie can play in a way to take all of Elsie's marbles.
1 20 8 2 3 5 3 5 3 5 3 5 3 5 3 5 3 5 3 5
Even Even Even Odd Even Odd Even Odd