금고털이

=== 작전 기술 브리핑, 2002/11/02 06:42 CST ===

"목표물은 도서관 2층 그림 뒤에 있는 클라인(Klein) 금고에 잠겨 있다. 클라인 금고는 극히 드물다. 대부분은 클라인과 그의 공장과 함께 제2차 세계대전 때 파괴되었다. 다행히 연구부의 노(老) 브룸바우가 죽기 전에 클라인의 비밀을 알아내어 기록해 두었다.

클라인 금고에는 두 가지 특징이 있다. 하나는 숫자 대신 알파벳을 쓰는 조합 자물쇠이고, 다른 하나는 문에 새겨진 인용문이다. 클라인 인용문에는 항상 서로 다른 대문자가 5개 이상 12개 이하로(주로 문장의 첫 글자) 들어 있으며, 하나 이상의 숫자를 언급한다. 이 대문자들 중 다섯 개가 금고를 여는 조합을 이룬다. 인용문에 등장하는 모든 수의 자릿수를 적절히 조합하면 하나의 목표 수를 얻는다. (목표 수를 만드는 방법은 기밀이다.)

조합을 찾으려면, 각 글자를 알파벳에서의 순서 값으로 바꾸었을 때($A=1$, $B=2$, ..., $Z=26$) 다음 식을 만족하는 다섯 글자 $v$, $w$, $x$, $y$, $z$를 골라야 한다. 그러면 조합은 문자열 $vwxyz$가 된다.

$v - w^2 + x^3 - y^4 + z^5 = T$

여기서 $T$는 목표 수이다. 식을 만족하는 조합이 여러 개라면, 사전순으로 가장 큰(사전에서 가장 뒤에 오는) 조합이 답이다.

예를 들어 목표 수 $T = 1$과 글자 집합 ABCDEFGHIJKL에 대해 FIECB는 하나의 해이다. $6 - 9^2 + 5^3 - 3^4 + 2^5 = 1$이기 때문이다. 이 목표 수에는 여러 조합이 성립하며, 그중 사전순으로 가장 큰 LKEBA가 답이다."

=== 작전 기술 지령, 전산과, 2002/11/02 12:30 CST ===

현장 배치를 위해 클라인 조합을 찾는 프로그램을 작성하라.

입력의 각 줄에는 천이백만보다 작은 양의 정수 목표 수 $T$, 공백 하나, 그리고 서로 다른 대문자 5개 이상 12개 이하가 차례로 주어진다. 마지막 줄에는 목표 수 $0$과 글자 END가 주어지며, 이 줄은 입력의 끝을 뜻하고 처리하지 않는다.

END로 끝나는 마지막 줄을 제외한 각 입력 줄마다 클라인 조합을 한 줄에 출력한다. 올바른 조합이 없으면 no solution을 출력한다.