GPS 부호화

전통적으로 간단한 암호는 알파벳의 한 순열을 정하고 각 문자에 01부터 26까지(또는 00부터 25까지) 번호를 매긴 뒤, 메시지를 숫자 문자열로 바꾸어 암호화한다. 그런 다음 문자열을 일정한 길이의 묶음으로 나누면 원문의 구조를 쉽게 감출 수 있다.

이 문제는 그 발상을 뒤집는다. 암호화하고 싶은 숫자 열(예를 들어 친구에게 보물이 숨겨진 위치를 알려 주기 위한 GPS 좌표)이 주어진다. 숫자 10개를 문자 10개로만 부호화하는 단순한 방법을 쓸 수도 있고, 26개의 문자를 모두 사용하여 남는 문자들로 적절한 두 자리 숫자 쌍을 부호화할 수도 있다. 예를 들어 941177은 9 4 1 1 7 7, 9 4 11 7 7, 또는 9 4 1 17 7로 부호화할 수 있다.

대문자의 한 순열이 주어진다. 이 순열은 0, 1, …, 25의 부호화를 암묵적으로 정의한다. 즉, 위치 i(0부터 셈)에 있는 문자는 수 i를 부호화한다. 0부터 9까지의 수는 한 자리 숫자를 나타낼 수 있고, 0부터 25까지의 수는 연속한 두 자리 숫자(값이 25 이하인 쌍이며 앞자리 0도 허용된다)를 나타낼 수 있다. 순열과 숫자 열이 주어졌을 때, 그 숫자 열을 문자열로 부호화하는 가장 짧은 방법을 구하여라. 이렇게 만든 문자열의 복호화가 유일하지 않을 수도 있음에 유의하라.

입력은 여러 개의 암호화 문제로 이루어진다. 각 문제는 대문자의 한 순열이 적힌 줄로 시작하고, 그 뒤로 각각 3자리 이상 20자리 이하의 숫자로 이루어진 문자열이 한 줄에 하나씩 이어진다. 한 문제의 숫자 문자열 목록은 0 하나만 있는 줄로 끝난다. 전체 입력은 # 하나만 있는 줄로 끝난다. 이 두 종료 줄은 처리하지 않는다.

각 문제마다 Problem 뒤에 문제 번호(1부터 시작하는 일련번호)를 붙인 줄을 출력한다. 이어서 그 문제의 각 숫자 문자열에 대해 가장 짧은 부호화를 한 줄에 하나씩 출력한다. 가장 짧은 길이의 부호화가 여러 개이면 사전순으로 가장 뒤에 오는(사전에서 가장 마지막에 나올) 것을 출력한다. 연속한 두 문제 사이에는 빈 줄을 하나 출력한다.