## BPC 1 S4 - Binary Matrices

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

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.

#### Input Specification

There is no input. The program you output should work for arbitrary initial values of and and will not know these values in advance.

#### Output Specification

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 standard checker. 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 identical checker.

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.

#### Scoring

Your score will depend on the total number of different registers your program accesses.

Number of registers usedScore          #### Sample Output

XOR C A 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.

Initial state:

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

After 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

After 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

After 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

After 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