Problem H
Nullary Computer
Brian Huck has invented a new power-saving computer. With the current CMOS-based processors, a certain amount of power is lost each time a bit is changed from $0$ to $1$ or back. To avoid this problem, Brian’s new Nullary Core stores only zeros. All numbers are stored in nullary form, as shown in the following table.
|
Decimal |
Nullary |
|
0 |
|
|
1 |
0 |
|
2 |
00 |
|
3 |
000 |
|
4 |
0000 |
|
5 |
00000 |
|
... |
... |
His initial $64$-nit model has $26$ registers, each of which may store up to (and including) $64$ nits, and any attempt to store more than $64$ nits will result in a run time error. There is also a flag register, which contains either a zero, or nothing. The instruction set is as follows:
|
Instruction |
Explanation and how to simulate in C |
|
A |
Add a zero to the value in register A (similarly for all uppercase letters). a++; |
|
a |
First, empty the flag register. Then, if possible, remove a zero from register A, and place it in the flag register (similarly for all lowercase letters) flag = 0; if(a>0) { flag=1; a--; } |
|
( |
If the flag register is empty, jump past the matching ). Otherwise, empty the flag register. while(flag) { flag=0; .... |
|
) |
Jump to the matching (. ... } |
Apart from instructions, no other characters than whitespace (which are ignored) are allowed in a nullary program.
To illustrate the elegance and simplicity of his computer, Brian has provided the following two example programs.
|
b(b)a(Ba) |
Move register A to register B (by first emptying register B, then repeatedly pulling a single zero from register A and placing it into B). |
|
XXXa(GIa)i(g(FY g)y(Gy)f(Zb(z)z (i(YBi)y(Iy))f) Zb(zb)z(xz)i)x |
Set the flag register if the number of zeros in register A is prime. |
Task
Your task is to write a sorting program for Brian’s Nullary Core-based Prototype Computer. The NCPC has limited memory, so your program must be no longer than $5432$ instructions. Also, the running time of your program must be no more than $5 \cdot 10^6$ steps for any possible input, where a step is considered to be the execution of one instruction.
The numbers to be sorted will be given in the first $24$ registers A-X; the remaining two registers (Y and Z) will be empty. After executing your sorting program, the sorted numbers should be in registers A through X, in increasing order. Registers Y and Z should be empty.
For example, if at the start of execution of your program the register values are as follows:
|
Reg. |
Value |
Reg. |
Value |
Reg. |
Value |
||
|
A |
0 |
J |
000 |
S |
|||
|
B |
000000000 |
K |
T |
||||
|
C |
000000 |
L |
U |
||||
|
D |
0000 |
M |
V |
||||
|
E |
00000000 |
N |
W |
||||
|
F |
0000000 |
O |
X |
0 |
|||
|
G |
0000 |
P |
Y |
||||
|
H |
000000 |
Q |
Z |
||||
|
I |
000000000 |
R |
Then after executing your program, the register values should be
|
Reg. |
Value |
Reg. |
Value |
Reg. |
Value |
||
|
A |
J |
S |
000000 |
||||
|
B |
K |
T |
000000 |
||||
|
C |
L |
U |
0000000 |
||||
|
D |
M |
V |
00000000 |
||||
|
E |
N |
0 |
W |
000000000 |
|||
|
F |
O |
0 |
X |
000000000 |
|||
|
G |
P |
000 |
Y |
||||
|
H |
Q |
0000 |
Z |
||||
|
I |
R |
0000 |
Note: any error with your Nullary program, whether it be syntactically incorrect, runs for too long, or crashes, will all result in a “Wrong Answer” judgement on Kattis, but detailed information about the cause of the error will be provided in the details for your submission.
Input
This problem has no input.
Output
Output the nullary source code of your sorting program.
