Our most famous programming language Quack is back to make this practice session an even more pleasant experience. For those who are new to IPSC (and didn't care to browse the archives before the contest) we will give an overview of the language.
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:
| operation | description |
|---|---|
| + | 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) |
| Command | Description |
|---|---|
| >[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. |
| Command | Description |
|---|---|
| :[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]. |
| Command | Description |
|---|---|
| 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. You may either download and compile it (you need a C++ compiler and STL to compile it) or use this web form. Please don't overuse the web form so that everyone gets a chance to use it.
Easy: Write a program to factorize in Quack.
The input is a positive number N (between 2 and 65535, inclusive) which is placed in the queue before your program is executed. Your program should output several lines, each containing a single number. Each of these numbers must be a prime, the product of the numbers must be N, and the numbers have to be printed in non-decreasing order.
For example, for N=12 your program is supposed to print three lines containing the numbers 2 2 3, respectively.
Your program will be tested on various inputs. To be accepted it has to solve all of them correctly.
(Note that you may test your program by simply writing the input number as the first line of the code.)
Hard: Write a program that duplicates the contents of the queue.
The input is a sequence containing at least one and at most 400 positive numbers. This sequence is placed in the queue before your program is executed. Your program should not output anything. After your program terminates the queue must contain exactly two copies of the input sequence, stored one after another.
For example, for the input sequence 1 2 3 4 your program is supposed to transform the contents of the queue to 1 2 3 4 1 2 3 4.
Execution of your program may not take more than one hundred thousand (100 000) steps to finish. If this limit is exceeded, the program will be terminated. In such case you will receive a message "Too many steps." and your submission will be rejected.
Credits:
Problemsetter(s): misof
Contest-related materials: misof