This is an output-only problem. You should not read anything from the input.
One day, errorgorn was setting problems for TOKI 24 but had no ideas. Suddenly, he remembered that prabowo and icypiggy were both involved in the preparation of IOI Registers. So he thought "won't it be funny to literally set IOI registers". So he did. And now you have to solve it as the final problem in this contest.
Unlike IOI registers, you will be performing your operations on a computer with a very unique way of storing integers. The computer has \(100\) registers, numbered from \(0\) to \(99\), where the \(i\)-th register is referred to as \(reg[i]\).
However, unlike a regular computer, each register stores a number in base Fibonacci which can be modelled as a binary string of length \(32\). The value, \(v(reg[i])\) of a register is the sum of \(reg[i][j] \cdot f[j]\), where \(f[j]\) is defined with \(f=1\), \(f=2\) and \(f[j]=f[j-1]+f[j-2]\).
For example \(v(\ldots 0011)=1+2=3\) and \(v(\ldots 00100100)=3+13=16\).
This computer supports the following arithmetic operations:
a = b & c)
a = b | c)
a = b ^ c)
a = ~b)
a = b << d)
a = b >> d)
where \(a\), \(b\), and \(c\) (\(0 \le a, b, c \le 99\)) are the register ids (not necessarily different) and \(d\) (\(1 \leq d \lt 32\)) is the shift exponent.
Additionally, the sample grader (explained below) supports another operation to help you test your solution:
This operation will be ignored by the actual grader and will not contribute to the number of arithmetic operations used.
You will have to write a simple program to add two numbers. There will be two binary strings of length \(10\), \(A\) and \(B\). Initially, all registers will be set to \(0\), then we will set \(reg[0 \ldots 9]=A\) and \(reg[0 \ldots 9]=B\).
Let \(reg'\) be the state of the registers after applying all the operations. The grader will check that \(v(reg)+v(reg)=v(reg')\).
You can only use \(500\) arithmetic operations or the computer will crash. Can you solve this problem?
No input is given on this problem.
The first line contains \(t\) (\(0 \le t \le 1000\)), the number of operations (includes arithmetic operations and print operations).
Each of the next \(t\) lines contains a single operation in the format given from the description.
Note that spacing does not matter in this problem. You can format
99 = 0 & 12 as
99 = 0&12. But
99 = 00 & 12,
99 = 0 & 012 and
99 = 0 && 12 will not be accepted. Also, you should not print empty lines between operations.
7 2 = 0 & 1 42 = 0 | 1 69 = 0 ^ 1 .69 0 = ~0 0 = 0 >> 1 2 = 1 << 1
Although \(7\) operations are used, only \(6\) are counted as arithmetic operations.
The sample will only be tested on the input \(A=000000011\) and \(B=0000000101\). The sample output is correct for this test.
The sum of values of register \(0\) and \(1\) initially is \(3+4=7\).
2 = 0 & 1applies \(reg=\ldots 00001\)
42 = 0 | 1applies \(reg=\ldots 00111\)
69 = 0 ^ 1applies \(reg=\ldots 00110\)
.69will be ignored in the real grader
0 = ~0applies \(reg=\ldots 11100\)
0 = 0 >> 1applies \(reg=01111 \ldots 11110\)
2 = 1 << 1applies \(reg=\ldots 01010\)
After all operations are applied, the value of register \(2\) is \(7\). So this sequence of operations is correct.
A sample grader (written in C++) is provided to aid you in testing. The sample grader reads the operations from a file
out.txt and takes in the arguments for \(A\) and \(B\) from stdin.
The sample grader can be compiled and run by the following commands:
g++ -std=c++17 -O2 -o grader sample_grader.cpp ./grader
The format of the operations in the file
out.txt are exactly the same as that described in the output.
The arguments given in stdin follow the format:
where \(A\) and \(B\) are binary strings of length \(10\).