비트 반전 (Hard)

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

요약

8비트 레지스터 기계에서 명령 300개 이하, not 명령 두 번 이하로 19개의 비트를 입력받아 각 비트를 반전해 출력하는 프로그램을 작성한다.

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

문제

과학자를 꿈꾸는 클레오파시는 최근 새 프로세서를 개발했다. 이 프로세서에는 A부터 Z까지 이름 붙은 26개의 레지스터가 있다. 각 레지스터는 8비트 부호 없는 정수 변수다.

이 새 프로세서는 놀랍도록 단순하다. 아래 표에 나온 명령어만 지원한다. (모든 명령어에서 R은 레지스터 이름, C는 상수, X는 레지스터 이름이나 상수다. 모든 상수는 8비트 부호 없는 정수, 즉 0부터 255까지의 수다.)


구문	의미
`and R X`	`R`과 `X`의 값을 비트 단위 and 연산하고, 결과를 `R`에 저장한다.
`or R X`	`R`과 `X`의 값을 비트 단위 or 연산하고, 결과를 `R`에 저장한다.
`not R`	`R`의 값을 비트 단위 not 연산하고, 결과를 `R`에 저장한다.
`shl R C`	`R`의 값을 왼쪽으로 `C`비트 시프트하고, 결과를 `R`에 저장한다.
`shr R C`	`R`의 값을 오른쪽으로 `C`비트 시프트하고, 결과를 `R`에 저장한다.
`mov R X`	`X`의 값을 `R`에 저장한다.
`get R`	8비트 부호 없는 정수를 읽어 `R`에 저장한다.
`put R`	레지스터 `R`의 내용을 8비트 부호 없는 정수로 출력한다.

참고:

not을 제외한 모든 명령어에서 두 번째 인자가 레지스터 이름이면, 그 내용은 변하지 않는다.
shl이나 shr이 호출될 때마다 첫 번째 인자의 값은 한쪽 끝이 잘리고 다른 쪽 끝이 0으로 채워진다. 예를 들어 X가 이진수 10110110이면 X shr 2는 00101101이다.

예시 작업

입력에 임의의 두 8비트 부호 없는 정수 a와 b가 들어 있다고 하자. 이 수를 읽고 z = 0인 것과 a = b인 것이 동치가 되도록 정수 z를 출력하는 프로그램을 작성하라. (즉, a와 b가 다르면 z는 양수여야 한다.)

문제 명세

각 데이터 세트마다 클레오파시의 프로세서에서 다음 작업을 수행하는 프로그램을 작성해야 한다. 프로그램의 입력은 정수들의 수열이고, 각 정수는 0 또는 1이다. 프로그램의 출력은 그 수열의 부정을 순서대로 나열한 수열이어야 한다. (즉, 각 0을 1로, 각 1을 0으로 바꾼다.)

수열에는 정확히 19개의 정수가 들어 있다. 프로그램에서 not 명령어는 최대 두 번까지만 사용할 수 있다. 프로그램은 최대 300개의 명령어로 이루어질 수 있다.

입력

이 문제에는 입력이 없다.

출력

프로그램을 일반 ASCII 텍스트로 제출하라. 텍스트의 각 줄은 완전한 명령어 하나를 포함하거나 공백만으로 이루어질 수 있다. 올바른 프로그램이 아닌 것을 제출하면 "틀렸습니다"로 판정되고 그에 맞는 오류 메시지를 받는다.

힌트

가능한 해법은 많다. 우리 해법에서는 입력을 레지스터 A와 B에 읽고, 두 값의 비트 단위 xor를 레지스터 Z에 계산해 출력한다.

그러나 xor 명령어는 없다. and, or, not을 조합해 만들어야 한다. 먼저 (not-A and B)를 C에, (not-B and A)를 D에 만든다. 마지막으로 (C or D)를 Z에 저장하면 끝난다.

왜 동작할까? 두 수가 같으면 C와 D가 모두 0이므로 Z도 0이다. 두 수가 다르면 두 수의 이진 표현에서 서로 다른 자릿수 d를 생각하자. 이 자릿수가 A에서 0이면 B에서는 1이어야 한다. 그러면 C에서 1이고 따라서 Z에서도 1이다. 그리고 이 자릿수가 A에서 1이면 B에서는 0이어야 하고, D에서 1, Z에서 1이다.

예제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