Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Nullary Computer
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 228Accepted: 87Special Judge

Description

Brian Huck has invented a new powersaving computer. With the current CMOSbased 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 on the right.
DecimalNullary
0
1
2
3
4
5
...

0
00
000
0000
00000
...

His initial 64-nit model has 26 registers, each of which may store up to 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:
Table 1: NC Instruction Set
InstructionExplanation and how to simulate in C
AAdd a zero to the value in register A (similarly for all uppercase letters).
a++;
aFirst, 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 are allowed in a nullary program.
Sample programs
Brian has provided some programs to illustrate the elegance and simplicity of his computer.
Your task will be to write a sorting program for Brian's Nullary Corebased 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 * 106 steps for any possible input, where a step is considered to be the execution of one instruction.
Table 2: Sample NC 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(FYg)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.

Important note: You must submit some Java, C or C++ source code that generate the nullary source code of this program.
Input to your nullary program
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.
Output to your nullary program
The sorted numbers should be in registers A through X, in increasing order. Register Y and Z should be empty.
Sample Input to your nullary program
A 0
B 000000000
C 000000
D 0000
E 00000000
F 0000000
G 0000
H 000000
I 000000000
J 000
K
L
M
N
O
P
Q
R
S
T
U
V
W
X 0
Y
Z
Sample Output to your nullary program
A
B
C
D
E
F
G
H
I
J
K
L
M
N 0
O 0
P 000
Q 0000
R 0000
S 000000
T 000000
U 0000000
V 00000000
W 000000000
X 000000000
Y
Z

Input

No input

Output

Output some Java, C, C++ or Pascal source code that generate the nullary source code of this program.

Sample Input

No input

Sample Output

Refer to Output.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator