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]⋅f[j], where f[j] is defined with f[0]=1, f[1]=2 and f[j]=f[j−1]+f[j−2].
For example v(…0011)=1+2=3 and v(…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≤a,b,c≤99) are the register ids (not necessarily different) and d (1≤d<32) is the shift exponent.
Additionally, the sample grader (explained below) supports another operation to help you test your solution:
.a
)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][0…9]=A and reg[1][0…9]=B.
Let reg′ be the state of the registers after applying all the operations. The grader will check that v(reg[0])+v(reg[1])=v(reg′[2]).
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≤t≤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
or 99 = 0&12
. But99 = 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 & 1
applies reg[2]=…0000142 = 0 | 1
applies reg[42]=…0011169 = 0 ^ 1
applies reg[69]=…00110.69
will be ignored in the real grader0 = ~0
applies reg[0]=…111000 = 0 >> 1
applies reg[0]=01111…111102 = 1 << 1
applies reg[2]=…01010After 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:
A B
where A and B are binary strings of length 10.
Subtask | Score |
---|---|
1 | 100 |