| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 7 | 5 | 5 | 71.429% |
Busy Beaver and Calico Bear are playing a game with an $N$ by $M$ grid of nonnegative integers $a_{i,j},ドル where initially no two edge-adjacent numbers are equal.
In a move, a player chooses a positive integer in the grid and decreases it by 1ドル,ドル subject to the constraint that after the move, it still holds that no two edge-adjacent numbers are equal and that all numbers are non-negative. If a player has no legal moves on their turn, they lose, and the other player wins.
Busy Beaver moves first, and then the players alternate. Assuming both players play optimally, determine whether or not Busy Beaver has a winning strategy.
Each test contains multiple test cases. The first line of input contains a single integer $T$ (1ドル \leq T \leq 10^4$) --- the number of test cases. The description of each test case follows.
The first line of each test case contains two positive integers $N$ and $M$ (1ドル \leq N, M, N \cdot M \leq 2.5 \cdot 10^5$) --- the dimensions of the grid.
The $i$-th of the next $N$ lines contains $M$ space-separated nonnegative integers $a_{i,1}, \dots, a_{i,M}$ (0ドル \leq a_{i,j} \leq 10^9$), where $a_{i,j}$ represents the integer in the grid in row $i$ and column $j$.
The sum of $N \cdot M$ over all test cases does not exceed 2ドル.5 \cdot 10^5$.
For each test case, output "Yes" (without quotes) if Busy Beaver wins, and "No" (without quotes) if Calico Bear wins.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | 0ドル \leq a_{i,j} \leq 100$. |
| 2 | 80 | No additional constraints. |
5 1 1 1 1 5 0 1 2 3 4 3 3 0 1 0 10 3 10 0 1 0 2 4 0 2 4 6 1 3 5 7 4 5 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7 6 7
Yes No Yes No No
In the first test case, Busy Beaver can decrease the 1ドル$ to a 0ドル$. Then, Calico Bear has no moves, so Busy Beaver has a winning strategy.
In the second test case, Busy Beaver has no legal moves. Therefore, Calico Bear has a winning strategy.
In the third test case, Busy Beaver first decreases the central 3ドル$ to a 2ドル$. Then, regardless of which 10ドル$ Calico Bear decreases, Busy Beaver can decrease the other one. Therefore, Calico Bear runs out of moves before Busy Beaver does, giving Busy Beaver a winning strategy.
University > MIT > M(IT)^2 > M(IT)^2 Winter 2025 Tournament > Beginner Round 7번