CF1672A.Log Chopping

传统题 时间 2000 ms 内存 256 MiB 3 尝试 1 已通过 1 标签

Log Chopping

题目描述

nn 根木头,第 ii 根木头的长度为 aia_i 米。由于劈木头很累,errorgorn 和 maomao90 决定玩一个游戏。

errorgorn 和 maomao90 轮流劈木头,errorgorn 先手。在每一回合,玩家选择一根木头,将其劈成 22 段。如果所选木头的长度为 xx,劈成的两段长度为 yyzz,则 yyzz 必须是正整数,并且 x=y+zx = y + z。例如,可以将长度为 33 的木头劈成长度为 2211 的两段,但不能劈成 330022221.51.51.51.5

无法进行劈木头操作的玩家判负。假设 errorgorn 和 maomao90 都采取最优策略,谁会获胜?

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 tt1t1001 \leq t \leq 100),表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含一个整数 nn1n501 \leq n \leq 50),表示木头的数量。

第二行包含 nn 个整数 a1,a2,,ana_1,a_2, \ldots, a_n1ai501 \leq a_i \leq 50),表示每根木头的长度。

注意,所有测试用例中 nn 的总和没有上限。

输出格式

对于每组测试用例,如果 errorgorn 获胜,输出 "errorgorn";如果 maomao90 获胜,输出 "maomao90"(不带引号)。

说明/提示

在第一个测试用例中,errorgorn 会获胜。最优操作是将长度为 44 的木头劈成两根长度为 22 的木头。此后只剩下 44 根长度为 22 的木头和 11 根长度为 11 的木头。

接下来,任何玩家唯一能做的操作就是将长度为 22 的木头劈成两根长度为 11 的木头。经过 44 次操作后,轮到 maomao90 时他将无法进行操作,因此 errorgorn 获胜。

在第二个测试用例中,errorgorn 在第一回合无法进行任何操作,会立即失败,因此 maomao90 获胜。

由 ChatGPT 4.1 翻译

样例

2
4
2 4 2 1
1
1
errorgorn
maomao90

在线编程 IDE

建议全屏模式获得最佳体验