비밀 코드: 가장 큰 수
시간 제한3초메모리 제한128 MB
잡음이 섞인 문자열에서 언어를 하나로 고정하거나 자릿수마다 다른 언어를 써도 되는 두 조건 아래 가능한 최대의 숫자를 부분열 매칭으로 찾는 문제입니다.
문제
스미스 요원은 비밀 센터로 하나의 양의 정수(0보다 큰 정수) 형태의 비밀 정보를 전송한다. 수를 부호화하기 위해, 그는 각 자리 숫자를 그에 대응하는 단어로 바꾼 뒤 그 단어들을 이어 붙인다. 예를 들어 42는 FOURTWO가 될 수 있다.
스미스는 네 개의 언어(1번, 2번, 3번, 4번)를 안다. 이 언어들에서 숫자 0부터 9까지는 다음과 같이 표기된다(모든 글자는 대문자 라틴 문자이며, ASCII 코드 65-90 범위이다).
부호화가 끝난 뒤, 그는 잡음을 덧붙인다. 즉, 불필요한 대문자 라틴 문자들을 추가한다. 이미 코드에 쓰인 문자를 포함해 어떤 문자든, 임의의 개수만큼, 임의의 위치에 넣을 수 있다.
이러한 코드를 읽어, 다음 두 가지 서로 다른 가정 아래에서 그 코드가 부호화할 수 있는 가장 큰 수를 구하는 프로그램을 작성하라.
- 어떤 언어를 썼는지는 모르지만, 위에 제시된 네 언어 중 하나의 같은 언어만 수 전체에 사용했다.
- 스미스는 자리마다 위에 제시된 네 언어 중 서로 다른 언어(또는 같은 언어)로 부호화했을 수 있다.
입력
입력은 여러 줄로 이루어지며, 각 줄을 독립적으로 처리한다. 각 줄은 최대 개의 대문자 라틴 문자로 이루어진 하나의 코드이다. 전체 입력의 크기는 1 MB 미만이다.
출력
입력의 각 줄에 대해, 위 두 가정에 따른 가장 큰 수를 그 순서대로 공백 하나로 구분하여 두 정수로 출력한다.
각 코드는 올바른 양의 정수(0이 아닌 정수)로부터 얻어졌음이 보장되므로, 두 답은 항상 양수이다. 앞자리 0 없이 출력한다.