Inverting bits (Hard)

시간 제한1초메모리 제한512 MB

요약

레지스터 26개와 8비트 연산만 있는 프로세서에서 not 명령을 최대 두 번만 써서 0과 1로 이루어진 19개 입력을 반대로 뒤집는 프로그램을 작성한다.

난이도: 보통10점 중 5점
유형: 비트 연산, 시뮬레이션, 구현
정답자: 아직 제출이 없습니다

문제

The wannabe scientist Kleofáš has recently developed a new processor. The processor has got 26 registers, labeled A to Z. Each register is an 8-bit unsigned integer variable.

This new processor is incredibly simple. It only supports the instructions specified in the table below. (In all instructions, R is a name of a register, C is a constant, and X is either the name of a register or a constant. All constants are 8-bit unsigned integers, i.e., numbers from 0 to 255.)


syntax	semantics
`and R X`	Compute the bitwise and of the values `R` and `X`, and store it in `R`.
`or R X`	Compute the bitwise or of the values `R` and `X`, and store it in `R`.
`not R`	Compute the bitwise not of the value `R`, and store it in `R`.
`shl R C`	Take the value in `R`, shift it to the left by `C` bits, and store the result in `R`.
`shr R C`	Take the value in `R`, shift it to the right by `C` bits, and store the result in `R`.
`mov R X`	Store the value `X` into `R`.
`get R`	Read an 8-bit unsigned integer and store it in `R`.
`put R`	Output the content of the register `R` as an 8-bit unsigned integer.

Notes:

After any instruction other than not, if the second argument was a register name, its content remains unchanged.
Whenever shl or shr is called, the shifted value of the first argument is truncated on one end and padded with zeroes on the other end. For example, if X equals to binary 10110110, then X shr 2 equals to 00101101.

Example task

Assume that the input contains an arbitrary two 8-bit unsigned integers a and b. Write a program that will read these numbers and produce an integer z such that z = 0 if and only if a = b. (That is, if a and b differ, z must be positive.)

Problem specification

For each data set, you have to write a program for Kleofáš’s processor that solves the following task: The input for your program is a sequence of integers, each of them a 0 or a 1. The output of your program must be a sequence of their negations, in order. (That is, change each 0 into a 1 and vice versa.)

The sequence contains exactly 19 integers. In your program, you may only use the instruction not at most twice. Your program can have at most 300 instructions.

입력

This problem has no input.

출력

Send us your program as a plain ASCII text. Each line of the text may either contain one complete instruction, or just whitespace. If you submit anything that is not a proper program, it will be judged “Wrong answer” and you will get an appropriate error message.

힌트

There are many possible solutions. In our solution, we read the input to registers A and B, compute their bitwise xor in register Z and output it.

However, we do not have an instruction for xor. We have to assemble it from ands, ors, and nots. First, we create (not-A and B) in C and (not-B and A) in D. Finally, we store (C or D) in Z and we are done.

Why does it work? If the two numbers are identical, then C and D will both be zero, and so will Z. If the two numbers are not identical, consider a digit d where the two numbers differ in their binary representations. If this digit is 0 in A, it has to be 1 in B. But then it is 1 in C and therefore it is 1 in Z. And if the digit is 1 in A, it has to be 0 in B, 1 in D, and 1 in Z.

예제1

예제 1

입력

예상 출력

get A
get B

mov C A
not C
and C B

mov D B
not D
and D A

mov Z C
or Z D

put Z