문제
2016년에 모든 양의 정수는 3개 이하의 회문 항(palindromic term)의 합으로 표현할 수 있다는 것이 증명되었다. 이 문제에서 회문 항이란, (선행 0이 없는) 숫자 문자열로서 양의 정수를 나타내며, 앞에서 읽으나 뒤에서 읽으나 같은 것을 의미한다.
양의 정수 S가 주어질 때, 합이 S가 되도록 하는 K개의 회문 항을 찾아라. 단, K는 최소가 되어야 한다.
입력
입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. 이어서 T줄이 주어지며, 각 줄에는 양의 정수 S가 하나씩 주어진다.
출력
각 테스트 케이스마다 다음 형식 중 하나로 한 줄을 출력하라.
회문 항이 1개만 필요하면 Case #x: A1,
2개가 필요하면 Case #x: A1 A2,
3개가 필요하면 Case #x: A1 A2 A3 형식이다.
여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고,
각 Ai는 위에서 정의한 회문 항이며,
Ai들의 합은 S와 같아야 한다.
예제
3
1
198
1234567890
Case #1: 1
Case #2: 191 7
Case #3: 672787276 94449 561686165
샘플 케이스 #1에서는 입력이 이미 회문이다.
샘플 케이스 #2에서는 예를 들어 99 99도 허용되는 답이라는 점에 유의하라. 99가 여러 번 등장하더라도 서로 다른 항으로 취급되므로, 이 해는 191 7과 같은 개수의 항을 사용한다.
또한 191 07, 181 8 9,
0110 88, 101 97, 7.0 191.0,
그리고 -202 4 등은 허용되는 답이 아니다.
출처
GCJ 2019wf C
로그인해야 코드를 작성할 수 있어요.