We can use an binary matrix to encode unsigned integers with bits in the following way: Let be the cell's value in the matrix at row and column . . The value represented by the binary matrix is the sum of for all . Less formally, the cell in the top left corner is the most significant bit, the cell in the row column is the second most significant, and the cell in the row column is the third most significant, etc.
You have pieces of memory called registers, where each register stores a binary matrix.
Each register is identified by an uppercase letter from to .
Registers and initially contain arbitrary values, while the rest contain all zeros.
You are to output a program that sorts and , setting
A := min(A, B) and
B := max(A, B).
You may use other registers in the process, but their final value does not matter.
Comparing two binary matrices is defined as comparing the integer values they represent.
You may only use instructions of the following types. All instructions first compute the value you would get by applying the operation on the two source operands, then set the destination operand equal to this value. All destination operands are registers, identified by a letter from to . Source operands can be registers or integer constants based on the type of operation. Integer constants must be in the range .
OR DST S1 S2- calculates the bitwise OR of matrices and .
AND DST S1 S2- calculates the bitwise AND of matrices and .
XOR DST S1 S2- calculates the bitwise XOR of matrices and .
LEFT DST S1 X2- shifts every bit in left by positions. Zeros will be shifted in from the right as necessary, setting the rightmost bits in each row to .
RIGHT DST S1 X2- shifts every bit in right by positions. Zeros will be shifted in from the left as necessary, setting the leftmost bits in each row to .
UP DST S1 X2- shifts every bit in up by positions. Zeros will be shifted in from the bottom as necessary, setting the bits closest to the bottom of each column to .
DOWN DST S1 X2- shifts every bit in down by positions. Zeros will be shifted in from the top as necessary, setting the bits closest to the top of each column to .
ADD DST S1 S2- performs row-wise addition on matrices and . Specifically, each row in each matrix is converted to a 32-bit integer, with the leftmost bit being the most significant, and corresponding rows from each matrix are added together. If the result of this addition is greater than or equal to for a specific row, the overflow bit is discarded. Note that, because of this, this operation is not equivalent to adding together the total values of the matrices.
There is no input. The program you output should work for arbitrary initial values of and and will not know these values in advance.
You should output at most instructions, each on a separate line. The instructions will be executed in the order you output them.
Additionally, the checker for this problem will have the same policy on whitespace as the
This means that trailing whitespace, empty lines, and missing a newline character at the end of the last line are tolerated.
This is required to allow the submission of plain text files (
Text language in the submission editor) since the editor strips trailing newline characters at the end of the file, which would make it impossible for plain text submissions to pass under an
You will receive a verdict of
Presentation Error if there was anything wrong with the format of your output.
You will only receive
Wrong Answer if your output corresponded to a set of valid instructions and it sorted the values in registers and incorrectly.
Your score will depend on the total number of different registers your program accesses.
|Number of registers used||Score|
XOR C A B ADD D C B RIGHT Z C 2 DOWN Z Z 1
Explanation for Sample
The sample output would not receive AC on the problem since it does not sort the matrices in registers A and B. It is provided only to clarify the output format. Here is what the operations would do if registers stored matrices. Note that the real test data will only have registers containing matrices as specified earlier.
A B C D Z 0010 1100 0000 0000 0000 1101 0110 0000 0000 0000 0110 0000 0000 0000 0000 0010 1011 0000 0000 0000
XOR C A B:
A B C D Z 0010 1100 1110 0000 0000 1101 0110 1011 0000 0000 0110 0000 0110 0000 0000 0010 1011 1001 0000 0000
ADD D C B:
A B C D Z 0010 1100 1110 1010 0000 1101 0110 1011 0001 0000 0110 0000 0110 0110 0000 0010 1011 1001 0100 0000
RIGHT Z C 2:
A B C D Z 0010 1100 1110 1010 0011 1101 0110 1011 0001 0010 0110 0000 0110 0110 0001 0010 1011 1001 0100 0010
DOWN Z Z 1:
A B C D Z 0010 1100 1110 1010 0000 1101 0110 1011 0001 0011 0110 0000 0110 0110 0010 0010 1011 1001 0100 0001