컴파일러

어떤 팀이 목적을 하나로 줄인 작은 프로세서를 만들었다. 레이저 표시판에 수 하나를 띄우는 것이다.

메모리는 8비트 레지스터 A, X, Y 세 개와 깊이 제한이 없는 스택뿐이다. 프로그램이 시작될 때 레지스터에는 알 수 없는 값이 들어 있고 스택은 비어 있다. 덧셈 결과는 하위 8비트만 남는다.

프로세서가 이해하는 명령은 여섯 개다.

• PH <reg>: 레지스터(A, X, Y 중 하나)의 값을 스택에 넣는다.
• PL <reg>: 스택 맨 위의 값을 꺼내 레지스터에 넣는다. 스택이 비어 있으면 프로그램이 멈춘다.
• AD: 스택에서 값 두 개를 꺼내고, 두 값을 더한 결과의 하위 8비트를 스택에 넣는다.
• ZE <reg>: 레지스터를 0으로 만든다.
• ST <reg>: 레지스터를 1로 만든다.
• DI <reg>: 레지스터의 값을 레이저 표시판으로 보내고 종료한다.

디스크에는 명령을 최대 40개까지 쓸 수 있고, 40번째 줄 다음은 실행되지 않는다.

수 $N$이 주어지면 $N$을 표시하는 프로그램을 출력한다. 같은 수를 표시하는 프로그램은 여러 개이므로, 출력할 프로그램은 출력 규칙에서 하나로 정한다.

• 첫째 줄에 표시할 수 $N$이 주어진다. ($0 \le N \le 255$)

아래 규칙으로 정해지는 프로그램을 한 줄에 명령 하나씩 출력한다.

$N = 0$이면 첫째 줄에 ZE A, 둘째 줄에 DI A를 출력한다.

$N \ge 1$이면 레지스터 A에 1을 두고 레지스터 X에서 $N$을 만든다. $1 \le v \le 255$인 $v$에 대해 $f(v)$를 $f(1) = 1$, $f(2) = 2$, $f(3) = 3$과

$f(v) = \min_{2 \le m \le v} \left( m + (v \bmod m) + f(\lfloor v / m \rfloor) \right) \quad (v \ge 4)$

로 정의한다.

순서쌍 목록은 이렇게 모은다. $v = N$에서 시작해 $v \ge 4$인 동안, $f(v)$의 최솟값을 만드는 $m$ 중 가장 작은 것을 골라 순서쌍 $(m, v \bmod m)$을 목록 뒤에 붙이고 $v$를 $\lfloor v / m \rfloor$로 바꾼다. $v$가 3 이하가 된 시점의 값을 $a$라 하고, 붙인 순서쌍을 역순으로 나열한 것을 $(m_1, d_1), \dots, (m_k, d_k)$라 한다. 마지막에 붙인 순서쌍이 맨 앞에 온다.

프로그램은 다음 순서로 이루어진다.

1. ST A 한 줄
2. PH A $a$줄, AD $a - 1$줄, PL X 한 줄
3. $i = 1, 2, \dots, k$ 순서로, PH X $m_i$줄, PH A $d_i$줄, AD $m_i + d_i - 1$줄, PL X 한 줄
4. DI X 한 줄

레지스터 X는 $a$에서 시작해 $i = 1, \dots, k$ 순서로 $v \leftarrow m_i v + d_i$를 따르므로, DI X를 실행하는 순간 $N$을 담고 있다. 이 프로그램의 명령 개수는 40개를 넘지 않는다.