Palindrome Game

题目描述

Bessie 和 Elsie 正在玩一个石子堆游戏，初始时石子堆中有 $S$ 个石子（$1\le S<10^{10^5}$）。两头奶牛轮流行动，Bessie 先手。轮到某头奶牛时，她必须从石子堆中移除 $x$ 个石子，其中 $x$ 必须是由该奶牛选择的任意正整数回文数。如果某头奶牛开始自己回合时石子堆为空，则该奶牛失败。 定义： 正整数如果从左向右与从右向左读起来相同，则称为回文数；回文数的例子包括 1、121 和 9009。不允许有前导零；例如，990 不是 回文数。 共有 $T$（$1\le T\le 10$）组相互独立的测试用例。对于每个测试用例，如果两头奶牛都采取最优策略，输出谁会赢得游戏。

输入格式

第一行包含 $T$，表示测试用例数量。接下来 $T$ 行描述这些测试用例，每个测试用例一行。 每个测试用例由一个整数 $S$ 指定。

输出格式

对于每个测试用例，如果从大小为 $S$ 的石子堆开始并在最优策略下 Bessie 获胜，则输出 B；否则输出 E。每个结果占一行。

3
8
10
12

B
E
B

提示

对于第一个测试用例，Bessie 可以在第一步移除所有石子，因为 $8$ 是回文数，从而保证获胜。 对于第二个测试用例，$10$ 不是回文数，因此 Bessie 不能在第一步移除所有石子。无论 Bessie 第一步移除多少石子，Elsie 总能在第二步移除剩余的所有石子，从而保证获胜。 对于第三个测试用例，可以证明在最优策略下 Bessie 获胜。 评分： 输入 2-4：$S<100$ 输入 5-7：$S<10^6$ 输入 8-10：$S<10^9$ 输入 11-13：无额外限制。 题目作者：Nick Wu

标签: USACO|2024|Bronze

来源

USACO|2024|Bronze