레이팅 미적용베시와 엘시가 처음에 돌 \(S\)개 (\(1\le S<10^{10^5}\))가 있는 돌 더미로 게임을 한다. 두 소는 베시부터 시작하여 번갈아 가며 차례를 진행한다. 자기 차례가 되면 더미에서 돌 \(x\)개를 제거해야 하는데, \(x\)는 그 소가 고른 임의의 양의 정수 팰린드롬이다. 자기 차례가 시작될 때 더미가 비어 있으면 그 소가 진다.
정의: 양의 정수가 앞으로 읽으나 뒤로 읽으나 같으면 팰린드롬이다. 팰린드롬의 예로는 1, 121, 9009가 있다. 앞자리 0은 허용되지 않는다. 예를 들어 990은 팰린드롬이 아니다.
\(T\) (\(1\le T\le 10\))개의 독립적인 테스트 케이스가 주어진다. 각 테스트 케이스에 대해, 두 소가 모두 최적으로 플레이할 때 누가 이기는지 출력하여라.
출제: Nick Wu
배점
- 입력 2-4: \(S<100\)
- 입력 5-7: \(S<10^6\)
- 입력 8-10: \(S<10^9\)
- 입력 11-13: 추가 제약 없음.
출제: Nick Wu
첫째 줄에 테스트 케이스의 개수 \(T\)가 주어진다. 다음 \(T\)개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다.
각 테스트 케이스는 정수 \(S\) 하나로 주어진다.
각 테스트 케이스마다, 크기 \(S\)의 돌 더미로 시작해 최적 플레이 시 베시가 이기면 B, 그렇지 않으면 E를 새 줄에 출력한다.
3
8
10
12B
E
BFor the first test case, Bessie can remove all the stones on her first move,
since \(8\) is a palindrome, guaranteeing her win.
For the second test case, \(10\) is not a palindrome, so Bessie cannot remove all
the stones on her first move. Regardless of how many stones Bessie removes on
her first move, Elsie can always remove all remaining stones on her second move,
guaranteeing her win.
For the third test case, it can be proven that Bessie wins under optimal play.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > February > Bronze