[USACO24FEB] Palindrome Game B

Luogu
IDLGP10187
Time2000ms
Memory256MB
DifficultyP2
数学贪心博弈论USACO2024O2优化
Bessie 和 Elsie 正在使用一堆初始时共 $S$ 个石子($1\le S<10^{10^5}$)进行一个游戏。两头奶牛依次行动,Bessie 先行动。当轮到一头奶牛行动时,她必须从堆中取走 $x$ 个石子,其中 $x$ 是该奶牛选定的任意正整数回文数。如果当一头奶牛的回合开始时石子堆是空的,那么这头奶牛就输了。 **定义**:一个正整数如果从前向后和从后向前读相同,则该数为回文数;回文数的例子有 $1$,$121$ 和 $9009$。数不允许有前导零;例如,$990$ **不是**回文数。 有 $T$($1\le T\le 10$)个独立的测试用例。对于每一个测试用例,输出如果两头奶牛都采取最优策略,谁会赢得游戏。 ## Input 输入的第一行包含 $T$,为测试用例的数量。以下 $T$ 行为测试用例,每个测试用例一行。 每个测试用例均由一个整数 $S$ 指定。 ## Output 对于每一个测试用例输出一行,如果 Bessie 在最优策略下可以从一堆 $S$ 个石子的石子堆开始赢得游戏,则输出 `B`,否则输出 `E`。 [samples] ## Note ### 样例解释 对于第一个测试用例,Bessie 可以在第一次行动中取走所有石子,因为 $8$ 是回文数,使她获胜。 对于第二个测试用例,$10$ 不是回文数,因此 Bessie 无法在第一次行动中取走所有石子。无论 Bessie 第一回合取走多少石子,Elsie 总能在第二回合取走所有余下的石子,使她获胜。 对于第三个测试用例,可以证明在最优策略下 Bessie 可以获胜。 ### 测试点性质 - 测试点 $2-4$:$S<100$。 - 测试点 $5-7$:$S<10^6$。 - 测试点 $8-10$:$S<10^9$。 - 测试点 $11-13$:没有额外限制。
Samples
Input #1
3
8
10
12
Output #1
B
E
B
API Response (JSON)
{
  "problem": {
    "name": "[USACO24FEB] Palindrome Game B",
    "description": {
      "content": "Bessie 和 Elsie 正在使用一堆初始时共 $S$ 个石子($1\\le S<10^{10^5}$)进行一个游戏。两头奶牛依次行动,Bessie 先行动。当轮到一头奶牛行动时,她必须从堆中取走 $x$ 个石子,其中 $x$ 是该奶牛选定的任意正整数回文数。如果当一头奶牛的回合开始时石子堆是空的,那么这头奶牛就输了。 **定义**:一个正整数如果从前向后和从后向前读相同,则该数为回文数;回文",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10187"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bessie 和 Elsie 正在使用一堆初始时共 $S$ 个石子($1\\le S<10^{10^5}$)进行一个游戏。两头奶牛依次行动,Bessie 先行动。当轮到一头奶牛行动时,她必须从堆中取走 $x$ 个石子,其中 $x$ 是该奶牛选定的任意正整数回文数。如果当一头奶牛的回合开始时石子堆是空的,那么这头奶牛就输了。\n\n**定义**:一个正整数如果从前向后和从后向前读相同,则该数为回文数;回文...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments