|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||1024 MB||12||10||5||83.333%|
Last year, the IPSC contestants had a hard time to understand a piece of code written in PostScript. Our invesigation revealed that the main cause was the use of a stack. To make this year's problems easier, we decided to replace stacks with much more intuitive data structure: a queue.
A queue is a data structure that supports two operations: Put (insert an element into the queue) and Get (remove and return the element that has been in the queue for the longest time). Just like a queue in a shop – new customers are "inserted into the queue" at the end while the customer at the beginning of the queue is served and leaves.
We will define a simple programming language Quack. Quack uses a single queue to store (almost) all the data. At the start of the program, this queue is empty. The only data type in Quack is number: an integer from the range 0-65535. All mathematical operations are computed modulo 65536. (For example, 65530+10=4.) In addition to the queue, Quack has 26 registers denoted by lowercase letters (i.e. a-z). Each register holds one number.
A program is a sequence of commands separated by whitespaces. The first character determines the command, optionally followed by parameters. The commands are defined below:
|+||Addition: get x, get y, put (x+y) modulo 65536.|
|-||Subtraction: get x, get y, put (x-y) modulo 65536.|
|*||Multiplication: get x, get y, put (x*y) modulo 65536.|
|/||Integer division: get x, get y, put x div y. (y mustn't be zero)|
|%||Modulo: get x, get y, put x modulo y. (y mustn't be zero)|
|>[register]||Get into register: get x, set the value of [register] to x.|
|<[register]||Put from register: put the value of [register].|
|P||Print: get x, print x to the standard output, print a newline.|
|P[register]||Print register: print the value of [register] to the standard output, print a newline.|
|C||Print as char: get x, print the character with ASCII code x modulo 256 to the standard output.|
|C[register]||Print register as char: print the character with ASCII code x modulo 256 (where x is the value of [register]) to the standard output.|
|:[label]||Label: this line of the program has the label [label].|
|J[label]||Jump (unconditional): the execution of the program continues on the line with the label [label].|
|Z[register][label]||Jump if zero: if the value of [register] is zero, the execution of the program continues on the line with the label [label].|
|E[register1][register2][label]||Jump if equal: if the values of [register1] and [register2] are equal, the execution of the program continues on the line with the label [label].|
|G[register1][register2][label]||Jump if greater: if the value of [register1] is greater than the value of [register2], the execution of the program continues on the line with the label [label].|
|Q||Quit: terminate the execution of the program. The program also terminates if the instruction pointer reaches the end of the program.|
|[number]||Put a number: If the first letter of a command doesn't match any of the previous lines, try to convert the command to a number and put in in the queue.|
The following program computes the sum 1 + 2 + ... + 20.
20 0 :start >a Zaend <a <a 1 + - >b <b Jstart :end P
Every time the execution of this program reaches the third line (the line with the label "start"), the queue contains exactly two numbers: the first is N, the second is the sum (N+1) + ... + 20. The number N is loaded into the register a. If it is already zero, the program jumps to the line with the label "end", prints the computed sum, and quits. Otherwise, we want to add N to the partial sum and decrease it. After the eighth instruction (put 1) the queue contains the values: PartialSum, N, N, 1. The following two instructions compute PartialSum+N and N-1. Finally, we place them in the correct order and repeat the loop.
For your convenience we provide you with an interpreter of this programming language.
Write a sorting program in Quack. The input is a sequence of positive numbers which is placed in the queue before your program is executed. Your program should print these numbers in non-descending order. Your program will be tested on various sequences. Each sequence will contain at least 1 and at most 250 numbers. (Note that you may test your program by simply writing the input sequence as the first few lines of the code.)
Execution of your program may not take more than one million steps to finish. If this limit is exceeded, the program will be terminated. In such case your submission will be rejected.