레이팅 미적용베시와 엘시가 무블(Moorbles) 게임을 하고 있다. 게임은 다음과 같이 진행된다. 베시와 엘시는 각각 얼마간의 구슬을 가지고 시작한다. 베시가 자신의 구슬 \(A\)개를 발굽에 쥐어 내밀면, 엘시는 \(A\)가 짝수(Even)인지 홀수(Odd)인지 맞힌다. 엘시가 맞히면 베시에게서 구슬 \(A\)개를 얻고, 틀리면 자신의 구슬 \(A\)개를 베시에게 잃는다 (엘시의 구슬이 \(A\)개보다 적으면 구슬을 전부 잃는다). 구슬을 전부 잃은 쪽이 진다.
게임이 몇 차례 진행된 뒤, 엘시에게는 구슬이 \(N\) \((1 \leq N \leq 10^9)\)개 있다. 엘시는 이기기는 어렵다고 생각하지만, 지지 않는 것을 목표로 플레이하고 있다. 베시와 오래 지내 온 덕분에 엘시는 베시의 습관을 잘 파악하고 있어서, 턴 \(i\)에 베시가 내밀 수 있는 구슬 개수는 \(K\) \((1 \leq K \leq 4)\)가지뿐임을 알고 있다. 베시가 지루해져서 게임을 그만두기까지 남은 턴은 \(M\) \((1 \leq M \leq 3 \cdot 10^5)\)번뿐이다. 베시가 어떻게 플레이하든 엘시가 지지 않는, 사전순으로 가장 작은 턴 수열을 찾을 수 있겠는가?
출제: Suhas Nagar
배점
- 입력 3: \(M \leq 16\).
- 입력 4-6: \(M \leq 1000\).
- 입력 7-12: 추가 제약 없음.
출제: Suhas Nagar
첫째 줄에 테스트 케이스의 개수를 나타내는 정수 \(T\) (\(1 \leq T \leq 10\))가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.
- 먼저 한 줄에 엘시가 가진 구슬의 개수, 턴의 수, 베시가 낼 수 있는 수의 가짓수를 각각 나타내는 세 정수 \(N\), \(M\), \(K\)가 주어진다.
- 그다음 \(M\)개의 줄이 주어지며, \(i\)번째 줄에는 턴 \(i\)에 베시가 낼 수 있는 구슬 개수를 나타내는, 공백으로 구분된 서로 다른 정수 \(K\)개 \(a_{i,1} \; a_{i,2} \ldots a_{i,K}\) (\(1 \leq a_{i, j} \leq 10^3\))가 주어진다.
모든 테스트 케이스에 대한 \(M\)의 합이 최대 \(3 \cdot 10^5\)임이 보장된다.
각 테스트 케이스마다, 엘시가 지지 않음을 보장하는 사전순으로 가장 작은 수 수열을 출력하거나, 질 수밖에 없다면 \(-1\)을 출력한다. 수 수열은 한 줄에 "Even" 또는 "Odd"인 \(M\)개의 토큰을 공백으로 구분하여 출력해야 한다.
참고: "Even"이 "Odd"보다 사전순으로 작다.
2
10 3 2
2 5
1 3
1 3
10 3 3
2 7 5
8 3 4
2 5 6Even Even Odd
-1In 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 5Even Even Even Odd Even Odd Even Oddriseoj 작성
출처 올림피아드 > USACO > 2023-2024 > February > Silver