2028: [USACO 2024 February Contest Silver] Problem 3. Moorbles

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\le N\le {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\le K\le 4)$ different amounts of marbles that Bessie may put out. There are only $M$ $(1\le M\le 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?

• First, one line containing three integers $N$, $M$, and $K$, representing the number of marbles Elsie has, the number of turns, and the number of potential moves Bessie can make respectively.
• Then, $M$ lines where line $i$ contains $K$ distinct space separated integers $a_{i,1}{a}_{i,2}\dots a_{i,K}$ ($1\le a_{i,j}\le {10}^3$) representing the possible amounts of marbles that Bessie might play on turn $i$.

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