어셈블리 코드

Jamshid는 특수한 계산 기계를 다루고 있다. 이 기계는 32비트 부호 없는 정수에 대한 연산만 지원하며, 메모리는 길이 2^32인 배열 M이다(0 ⩽ i < 2^32에 대해 M_i는 32비트 부호 없는 정수).

기계의 어셈블리 코드는 다음 주소 지정 방식을 지원한다.

• 즉시 주소 지정: #⟨number⟩ 상수 값을 나타낼 때 쓴다. 예를 들어 #3은 상수 3을 뜻한다.
• 직접 주소 지정: $⟨index⟩ 메모리 셀을 직접 지정할 때 쓴다. 예를 들어 $7은 셀 M_7을 가리킨다.
• 간접 주소 지정: @⟨index⟩ 포인터를 지원하기 위한 방식이다. 먼저 ⟨index⟩로 지정된 메모리 셀의 값을 읽고, 그 값이 지정하는 셀을 가리킨다. 예를 들어 M_5 = 9이면 @5는 M_9를 가리킨다.

프로그램이 실행되기 시작할 때 모든 메모리 셀은 0으로 초기화된다.

기계의 어셈블리 코드는 명령의 나열이다. 각 명령은 연산 하나와 그 뒤에 오는 여러 주소로 이루어진다. 현재 기계의 어셈블리 언어가 지원하는 연산은 다음과 같다.

• MOVE ⟨dest⟩ ⟨source⟩: ⟨source⟩가 가리키는 값을 ⟨dest⟩가 가리키는 메모리 셀에 복사한다. 예를 들어 MOVE $9 #13은 M_9를 13으로 만들고, MOVE @4 $6은 M_{M_4}를 M_6의 값으로 만든다.
• INPUT ⟨address⟩: 입력에서 수 하나를 읽어 ⟨address⟩가 가리키는 메모리 셀에 저장한다. 예를 들어 INPUT $2는 입력값을 M_2에 저장하고, INPUT @1은 입력값을 M_{M_1}에 저장한다.
• OUTPUT ⟨address⟩: ⟨address⟩가 가리키는 값을 출력에 인쇄한다.
• ADD ⟨dest⟩ ⟨arg1⟩ ⟨arg2⟩: ⟨arg1⟩과 ⟨arg2⟩가 가리키는 값의 합을 ⟨dest⟩가 지정하는 메모리 셀에 넣는다. 산술 오버플로가 나면 결과를 2^32로 나눈 나머지가 목적지에 저장된다. 예를 들어 ADD @10 #4294967290 #10은 M_{M_{10}}을 4로 만들고, ADD $20 @8 $9는 M_20을 M_{M_8} + M_9로 만든다.
• MULT ⟨dest⟩ ⟨arg1⟩ ⟨arg2⟩: ADD와 비슷하게 곱셈을 수행한다. 산술 오버플로가 났을 때의 동작도 같다.
• AND ⟨dest⟩ ⟨arg1⟩ ⟨arg2⟩: ⟨arg1⟩과 ⟨arg2⟩가 가리키는 값의 비트 AND를 ⟨dest⟩가 지정하는 메모리 셀에 넣는다. 예를 들어 AND $15 $33 #7은 M_33을 8로 나눈 나머지를 M_15에 넣는다.
• OR ⟨dest⟩ ⟨arg1⟩ ⟨arg2⟩: AND와 비슷하게 비트 OR를 적용한다. 예를 들어 OR $121 $121 #1은 M_121이 짝수이면 값을 1 증가시킨다.
• XOR ⟨dest⟩ ⟨arg1⟩ ⟨arg2⟩: AND와 비슷하게 비트 XOR를 적용한다. 예를 들어 XOR @11 #52 #37은 M_{M_{11}}을 17로 만든다.

OUTPUT 연산을 제외하면 모든 연산에 주어지는 첫 번째 주소는 직접 또는 간접 주소여야 한다. 위 연산을 사용해 Jamshid는 기계용 어셈블리 코드를 작성했다. 이 코드는 입력에서 여러 수를 읽고 정수 하나를 출력에 쓴다(프로그램에는 OUTPUT 명령이 정확히 하나 있다). Jamshid는 k개의 서로 다른 입력 집합으로 프로그램을 실행해 결과를 저장했다. 나중에 그의 코드에 포매팅 스크립트를 돌렸는데, 스크립트의 버그 때문에 어셈블리 프로그램의 일부가 손상되었다. 더 구체적으로, 5개의 산술 및 비트 연산(ADD, MULT, AND, OR, XOR)이 서로 다른 5개의 ASCII 문자 A, B, C, D, E로 대체되었다. 문제는 각 ASCII 문자가 어떤 연산을 나타내는지 분명하지 않다는 점이다. 손상된 프로그램과 k개의 입력 집합 및 그 결과가 주어질 때, 5개의 어셈블리 연산을 5개의 ASCII 문자에 대응시키는 방법을 Jamshid가 찾도록 도와야 한다.

입력은 손상된 어셈블리 프로그램으로 시작한다. 프로그램의 각 줄에는 앞에서 설명한 형식의 명령 하나가 들어 있다. 프로그램에는 명령이 최대 100개 있다. 마지막 명령이 프로그램의 유일한 출력 연산임이 보장된다. 다음 줄에는 정수 k가 하나 들어 있다(1 ⩽ k ⩽ 100). 그다음 k개 줄은 각각 프로그램의 실행 로그를 지정하는, 공백으로 구분된 정수 나열이다. 프로그램에 주어진 입력 수의 나열 뒤에 프로그램 출력이 붙은 형태다. 입력에 있는 모든 수는 2^32보다 작은 음이 아닌 정수이다.

첫 줄에 5개의 어셈블리 연산을 5개의 ASCII 문자에 대응시키는 서로 다른 방법의 수를 정수 하나로 출력한다. 이 결과는 1과 120 사이의 수일 수 있다. 결과가 하나뿐이면 두 번째 줄에 그 대응을 출력해야 한다. 이때 ADD, MULT, AND, OR, XOR 연산을 공백으로 구분한 순열로 출력하며, 순서는 각각 ASCII 문자 A, B, C, D, E로 대체된 순서와 같아야 한다.