지급 시스템
시간 제한1초메모리 제한128 MB
거대한 계좌 잔액이 주어질 때, 왼쪽에서 오른쪽으로 계산한 값은 한도를 넘지 않으면서 오른쪽에서 왼쪽으로 계산한 실제 거듭제곱 값을 최대화하는 수식을 구성하고, 동률이면 사전순으로 가장 작은 답을 찾아야 합니다.
문제
광천수 생산 대학교의 지급 시스템은 완전히 자동화되어 있고(전부 토마토 프로그래밍 언어로 작성되었습니다), 출금하려는 금액을 입력하면 됩니다. 교수들의 급여가 워낙 높다 보니 금액을 ^ 연산자를 써서 지수 형태로 입력할 수도 있습니다. 예를 들어 16 MWU(광천수 단위, mineral water units)를 출금하려면 16, 2^4, 2^2^2 중 무엇으로 입력해도 됩니다.
어느 날 잔액이 80 MWU였던 스타네스쿠가 2^3^2를 입력했는데, 80보다 많이 가져갈 수 없어야 함에도 놀랍게도 512 MWU를 받았습니다. 이 시스템은 두 개의 모듈로 이루어져 있습니다. 첫 번째 모듈은 계좌에 거래를 처리할 만큼의 돈이 있는지 확인하고, 두 번째 모듈은 실제로 돈을 내어 줍니다. 알고 보니 두 모듈은 ^ 연산자를 다르게 계산했습니다. 첫 번째 모듈은 왼쪽에서 오른쪽으로, 두 번째 모듈은 (수학적으로 올바른 방식인) 오른쪽에서 왼쪽으로 계산합니다. 그래서 첫 번째 모듈에서는 2^3^2 = (2^3)^2 = 64이지만, 두 번째 모듈에서는 2^3^2 = 2^(3^2) = 512입니다.
스타네스쿠가 이 시스템에서 가능한 한 많은 돈을 출금하도록 돕는 프로그램을 작성하세요. (혹시 이게 부당하다고 생각된다면, 광천수 생산 대학교는 원래 나쁘고 사악한 곳이니 안심하세요.)
입력
입력의 각 줄에는 스타네스쿠 계좌의 잔액이 하나씩 주어지며, 2 이상 10^100 − 1 이하의 정수입니다. 입력은 파일 끝(EOF)에서 종료됩니다.
출력
각 금액에 대해, 스타네스쿠가 가장 많은 돈을 받으려면 무엇을 입력해야 하는지 한 줄에 출력하세요. 입력 문자열은 다음을 만족해야 합니다.
- 정수들과 그 사이의
^연산자만으로 이루어져야 합니다. - 첫 번째 모듈의 검사를 통과하면서(왼쪽에서 오른쪽으로 계산한 값이 잔액을 넘지 않아야 합니다) 두 번째 모듈의 값(오른쪽에서 왼쪽으로 계산)이 가능한 한 커야 합니다.
- 숫자 1을 포함하면 안 됩니다(어차피 쓸모없습니다).
같은 최댓값을 주는 답이 여러 개면 첫 번째 숫자가 가장 작은 것을, 그래도 여러 개면 두 번째 숫자가 가장 작은 것을, 그런 식으로 출력하세요.