Moorbles

题目描述

Bessie 和 Elsie 在玩一个叫 Moorbles 的游戏。游戏规则如下： Bessie 和 Elsie 一开始各有一定数量的弹珠。Bessie 用蹄子握住她的 $A$ 颗弹珠，让 Elsie 猜测 $A$ 是 Even 还是 Odd。若 Elsie 猜对了，她从 Bessie 那里赢得这 $A$ 颗弹珠；若她猜错了，她会输给 Bessie $A$ 颗弹珠（如果 Elsie 的弹珠少于 $A$，则她输掉自己所有的弹珠）。当一名玩家失去所有弹珠时即判负。 在游戏进行了若干回合后，Elsie 拥有 $N$ $(1 \leq N \leq 10^9)$ 颗弹珠。她觉得想赢很难，但她的目标是不输。由于经常和 Bessie 相处，Elsie 很了解 Bessie 的习惯，并发现第 $i$ 回合时，Bessie 只可能拿出 $K$ $(1 \leq K \leq 4)$ 种不同数量的弹珠。Bessie 在感到无聊并停止游戏之前，一共只会玩 $M$ $(1 \leq M \leq 3 \cdot 10^5)$ 个回合。 你能否找出一个按字典序最小的回合选择序列，使得无论 Bessie 如何出牌，Elsie 都不会输？

输入格式

第一行包含一个整数 $T$ ($1 \leq T \leq 10$)，表示测试用例数量。每个测试用例如下描述： 首先，一行包含三个整数 $N$, $M$, $K$，分别表示 Elsie 拥有的弹珠数、回合数、以及 Bessie 每回合可能的出牌数量种类数。 然后有 $M$ 行，其中第 $i$ 行包含 $K$ 个互不相同的、以空格分隔的整数 $a_{i,1} \; a_{i,2} \ldots a_{i,K}$ ($1 \leq a_{i, j} \leq 10^3$)，表示 Bessie 在第 $i$ 回合可能拿出的弹珠数量。 保证所有测试用例的 $M$ 之和不超过 $3 \cdot 10^5$。

输出格式

对于每个测试用例，输出 Elsie 为保证不输所需的按字典序最小的行动序列；如果她一定会输，则输出 $-1$。行动序列应输出在一行上，由 $M$ 个以空格分隔的标记组成，每个标记为 "Even" 或 "Odd"。 注意："Even" 的字典序小于 "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

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

提示

在第一个样例中，唯一字典序更小的行动序列是 "Even Even Even"，但在这种情况下 Bessie 可以通过先出 $5$（使 Elsie 的弹珠从 $10$ 变为 $5$），再出 $3$（使 Elsie 的弹珠从 $5$ 变为 $2$），再出 $3$（清空她所有弹珠）来让 Elsie 输掉。 如果 Elsie 改为采用正确的行动序列 "Even Even Odd"，那么若 Bessie 仍按同样方式出牌，最后当她出 $3$ 时，Elsie 将赢得这 $3$ 颗弹珠，使她的弹珠数增加到 $5$。还可以进一步证明：在 Elsie 采用 "Even Even Odd" 的前提下，Bessie 无法通过其他出牌方式拿走 Elsie 的所有弹珠。 在第二个样例中，可以证明无论 Elsie 选择何种行动序列，Bessie 都能通过某种出牌方式拿走 Elsie 的所有弹珠。

SAMPLE INPUT: 1 20 8 2 3 5 3 5 3 5 3 5 3 5 3 5 3 5 3 5 SAMPLE OUTPUT: Even Even Even Odd Even Odd Even Odd

SCORING: Input 3: $M \leq 16$. Inputs 4-6: $M \leq 1000$. Inputs 7-12: No further constraints. Problem credits: Suhas Nagar

标签: USACO|2024|Silver

来源

USACO|2024|Silver