페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8141
서브태스크

정수 팰린드롬 돌게임 1s 1024MB

문제

갑돌이와 갑순이는 S개의 돌이 있는 더미에서 게임을 하고 있다. 두 사람은 번갈아 가며 돌을 빼고, 갑돌이가 먼저 시작한다. 각 턴에서, 각 사람은 자신이 선택한 x개의 돌을 더미에서 빼야 한다. 단, x는 양의 정수이며 정수 팰린드롬이어야 한다. 더미가 비어 있으면 그 턴을 시작한 사람이 지게 된다.

정수 팰린드롬은 앞에서부터 읽을 때와 뒤에서부터 읽을 때가 동일한 수이다.

예를 들어, 1, 121, 9009는 팰린드롬이다.

선행 0은 허용되지 않으며, 예를 들어 990은 팰린드롬이 아니다.

T개의 독립적인 테스트 케이스가 주어진다. 각 테스트 케이스에 대해, 두 사람이 최적 플레이를 할 경우, 게임에서 누가 이기는지 출력하라.


입력

첫 번째 줄에는 T가 주어진다. 테스트 케이스의 개수이다. (1 ≤ T ≤ 10)

다음 T줄에 각 테스트 케이스가 주어진다. 각 테스트 케이스는 하나의 정수 S로 주어진다. (1 ≤ S < 10^{10^5})


출력

각 테스트 케이스마다, 갑돌이가 최적 플레이를 할 때 이기면 B를, 그렇지 않으면 E를 새로운 줄에 출력한다.

  • 참고로, 갑돌이의 눈은 갈색(Brown)이고, 갑순이의 눈은 에메랄드색(Emerald)이다.


부분문제

번호 점수 조건
#140점

S<100

#230점

S<10^6

#320점

S<10^9

#410점

추가 제약 조건 없음


예제 

3
8
10
12
B
E
B

첫 번째 테스트 케이스에서는 갑돌이가 첫 번째 턴에서 8을 팰린드롬으로 볼 수 있기 때문에 모든 돌을 제거하고 이긴다.

두 번째 테스트 케이스에서는 10이 팰린드롬이 아니기 때문에 갑돌이는 첫 번째 턴에서 모든 돌을 제거할 수 없다. 갑돌이가 첫 번째 턴에서 몇 개의 돌을 빼더라도, 갑순이는 항상 두 번째 턴에서 남은 돌을 모두 제거하여 이긴다.

세 번째 테스트 케이스에서는 최적 플레이에서 갑돌이가 이긴다는 것을 증명할 수 있다.



출처

USACO 2024 February Bronze 1번

로그인해야 코드를 작성할 수 있어요.