Mimo & Yuyu

Forget the picture for a second. The important object is not the exact pile layout inside each cell. It is the number of tokens in each column.

Let $d_j$ be the number of tokens currently in column $j$.

A move starting from column $j$ removes one token from column $j$, and because the first step must go left, it never adds anything back to column $j$. It may add tokens only in columns $1,2,\ldots,j-1$.

So the game cannot run forever: if you look at

$$(d_m,d_{m-1},\ldots,d_2),$$

each move decreases the first changed entry in this high-to-low order. No infinite nonsense, no draw, normal game.

Case 1: $n=1$

There is only one row, so a token in column $c>1$ has only one valid move:

$$(c) \to (c-1),(c-2),\ldots,1.$$

Column $1$ tokens are dead.

Let $f(c)$ be the number of future turns caused by one token initially in column $c$.

Clearly:

$$f(1)=0, \qquad f(2)=1.$$

For $c\ge 3$, moving that token takes one turn and creates one token in every smaller column:

$$f(c)=1+\sum_{i=2}^{c-1} f(i).$$

This gives:

$$f(c)=2^{c-2}\quad(c\ge 2).$$

Only $f(2)=1$ is odd. Every token in column $3$ or later contributes an even number of turns. Since there is no real choice in this one-row game, the winner is just determined by the parity of the total number of turns.

So for $n=1$, Mimo wins iff the number of tokens in column $2$ is odd.

Case 2: $n\ge 2$

Now the clean claim is:

Yuyu wins exactly when every column $2,3,\ldots,m$ contains an even number of tokens.

Column $1$ still does not matter, because tokens there cannot move.

First, suppose every $d_j$ for $j\ge 2$ is even. Any legal move must start in some column $j\ge 2$. That move removes one token from column $j$, and adds nothing back to column $j$. Therefore $d_j$ becomes odd. So the player who moves from this state always gives the opponent a state with at least one odd non-dead column.

Now suppose some column $j\ge 2$ has odd token count. Let $J$ be the largest such column. We will move a token from column $J$ and make every non-dead column even.

Columns larger than $J$ are already even and will not be touched. Removing one token from column $J$ makes $d_J$ even. For each smaller column $i$ with $2\le i<J$, we want to add:

• $1$ token if $d_i$ is odd,
• $2$ tokens if $d_i$ is even.

Then every such column becomes even.

Why is this path always possible? Because $n\ge 2$ gives us two adjacent rows to snake through. Start from the chosen token at row $r$, column $J$. Pick a neighboring row $s$: if $r<n$, use $s=r+1$, otherwise use $s=r-1$.

After stepping left into column $J-1$, process columns from right to left:

• If this column needs $1$ token, visit only the current row in this column, then step left.
• If this column needs $2$ tokens, visit the current row, move vertically to the neighboring row, then step left from there.

That uses either one or two distinct cells in each column, never moves right, and eventually reaches column $1$. Column $1$ can receive whatever; it is dead anyway.

So every state with at least one odd column $2..m$ has a move to the all-even state. And every all-even state moves to a not-all-even state.

That is the whole game. No full Grundy table needed. Trying to compute one is bringing a spreadsheet to a knife fight.

Algorithm

For each test case:

• If $n=1$, toggle parity only for tokens in column $2$.
• If $n\ge 2$, toggle parity for every token whose column is at least $2$.
• If any relevant column has odd parity, print Mimo; otherwise print Yuyu.

The total number of tokens over all tests is at most $2\cdot 10^5$, so an $O(k\log k)$ parity set is easily fast enough.