자물쇠 따기

헝가리 국고는 금고 중 하나의 잠금장치를 교체했습니다. 이 새로운 자물쇠는 맞춤형 키카드로만 열 수 있습니다. 키카드 검증은 특별한 프로토콜을 따릅니다.

자물쇠에는 $0$부터 $N-1$까지 번호가 매겨진 $N$개의 내부 상태가 있습니다. $0$부터 $N-1$까지의 각 $i$에 대해, 상태 $i$에는 비트 $A[i]$와 두 상태 $S[i][0]$, $S[i][1]$이 연결되어 있습니다. 비트는 $0$ 또는 $1$인 이진 숫자입니다. 상태 $S[i][0]$과 $S[i][1]$은 같을 수도 있으며, 어떤 상태가 자기 자신과 연결될 수도 있습니다.

이와 비슷하게, 키카드에는 $0$부터 $M-1$까지 번호가 매겨진 $M$개의 상태가 있으며, $0$부터 $M-1$까지의 각 $j$에 대해 상태 $j$에는 비트 $B[j]$와 상태 $T[j][0]$, $T[j][1]$이 연결되어 있습니다. 이후 자물쇠 상태와 키카드 상태를 모두 상태라고 부릅니다.

검증 과정에서 자물쇠는 키카드와 짝을 이룹니다. 둘 다 비트를 출력할 수 있고, 상대방의 출력에서 비트를 읽을 수도 있습니다. 과정이 시작될 때 자물쇠는 특정 초기 상태 $i_0$으로 설정됩니다. 키카드 또한 그 키카드에 특정된 초기 상태 $j_0$으로 설정됩니다. 둘은 다음 단계들을 최대 $10^7$번 반복합니다.

1. 둘은 각각 현재 상태에 따라 비트 하나를 출력합니다. 자물쇠가 상태 $i$에 있으면 비트 $A[i]$를 출력합니다. 마찬가지로 키카드가 상태 $j$에 있으면 $B[j]$를 출력합니다.
2. 둘은 상대방이 출력한 비트를 읽습니다. 자물쇠는 $B[j]$를 읽고, 키카드는 $A[i]$를 읽습니다. 두 비트가 다르면 오류 하나를 기록합니다.
3. 장치들은 자신이 읽은 비트와 현재 상태에 연결된 상태들을 바탕으로 상태를 변경합니다. 자물쇠는 상태 $S[i][B[j]]$로 들어가고, 키카드는 상태 $T[j][A[i]]$로 들어갑니다.

검증 과정 중 어느 시점에서든 오류의 수가 $K$에 도달하면 검증이 실패하고 과정이 종료됩니다. 그렇지 않고 $K$개 이상의 오류를 기록하지 않은 채 $10^7$번의 반복을 완료하면 검증이 성공하고 자물쇠가 열립니다.

새 자물쇠를 설치할 때 기술자들이 실수했습니다. 검증 과정에 사용되는 초기 상태 $i_0$를 지정하는 것을 잊었습니다. 그 결과 자물쇠가 키카드와 짝을 이룰 때마다 임의의 (알 수 없는) 초기 상태로 설정됩니다.

여러분의 과제는 이 실수에도 불구하고 자물쇠를 열 수 있는 키카드를 만드는 것입니다.

구현 세부사항

다음 프로시저를 구현해야 합니다.

void construct_card(int N, int[] A, int[][] S)

• $N$: 자물쇠의 내부 상태 수입니다.
• $A$: 자물쇠의 상태들과 연결된 비트들을 지정하는 길이 $N$의 배열입니다.
• $S$: 길이 $2$의 배열들을 원소로 갖는 길이 $N$의 배열입니다. 자물쇠의 상태들과 연결된 두 상태를 지정합니다.
• 이 프로시저는 자물쇠의 초기 상태와 관계없이 자물쇠를 열 수 있는 키카드를 만들어야 합니다.
• 이 프로시저는 각 테스트 케이스마다 정확히 한 번 호출됩니다.

이 프로시저는 키카드를 만들기 위해 다음 프로시저를 정확히 한 번 호출해야 합니다.

void define_states(int M, int[] B, int[][] T, int j0)

• $M$: 키카드의 내부 상태 수입니다.
• $B$: 키카드의 상태들과 연결된 비트들을 지정하는 길이 $M$의 배열입니다.
• $T$: 길이 $2$의 배열들을 원소로 갖는 길이 $M$의 배열입니다. 키카드의 상태들과 연결된 두 상태를 지정합니다.
• j0: 키카드의 초기 상태를 나타내는 수입니다.
• 이 프로시저는 $M$개의 내부 상태를 갖는 키카드를 만듭니다. $0$부터 $M-1$까지의 각 $j$에 대해, 상태 $j$에는 비트 $B[j]$와 상태 $T[j][0]$, $T[j][1]$이 연결됩니다. 키카드의 초기 상태는 j0으로 설정됩니다.
• 이 프로시저는 construct_card 프로시저에 의해 정확히 한 번 호출되어야 합니다.

define_states의 매개변수에 대한 제약 조건은 아래의 제약 조건 절에 주어져 있습니다.

예제

$N=2$개의 상태를 갖는 자물쇠를 생각해 봅시다. 상태 $0$에는 비트 $A[0]=0$과 상태 $S[0][0]=1$, $S[0][1]=0$이 연결되어 있고, 상태 $1$에는 비트 $A[1]=1$과 상태 $S[1][0]=1$, $S[1][1]=0$이 연결되어 있습니다. 이 예제에서는 $K$의 값이 $2$라고 가정합니다.

construct_card 프로시저는 다음과 같이 호출됩니다.

construct_card(2, [0, 1], [[1, 0], [1, 0]])

먼저, $M=1$개의 상태를 갖고 $B[0]=1$, $T[0][0]=T[0][1]=0$이며 초기 상태가 $j_0=0$인 키카드를 생각해 봅시다.

자물쇠의 알 수 없는 초기 상태가 $1$인 경우, 검증 과정의 단계들은 다음 표와 같습니다. 자물쇠와 키카드의 상태는 각각 $i$와 $j$로 표시합니다.

마지막 두 열은 다음 단계에서의 자물쇠와 키카드의 상태를 나타낸다는 점에 유의하십시오.

단계 $0$에서는 $A[i]=B[j]$이므로 오류가 없음을 알 수 있습니다. 단계 $0$ 이후 단계 $1$과 단계 $2$에서 오류가 발생하므로 검증이 실패하고 과정이 종료됩니다. 따라서 이 키카드는 자물쇠를 열 수 없습니다.

$M=2$개의 상태를 갖고 $B=[0,1]$, $T=[[1,1],[0,0]]$이며 초기 상태가 $j_0=0$인 키카드를 생각해 봅시다.

자물쇠의 초기 상태가 $0$이면 검증은 다음과 같이 진행됩니다.

이 시점에서 검증 과정이 오류 없이 성공할 것임을 추론할 수 있습니다.

자물쇠의 초기 상태가 $0$이면 검증은 다음과 같이 진행됩니다.

이 시점에서 검증 과정이 추가 오류 없이 성공할 것임을 추론할 수 있습니다.

따라서 이 키카드는 자물쇠의 초기 상태와 관계없이 자물쇠를 열 수 있습니다. 프로시저는 다음과 같이 define_states를 호출할 수 있습니다.

define_states(2, [0, 1], [[1, 1], [0, 0]], 0)

define_states가 완료된 후 construct_card 프로시저는 반환해야 합니다.

제약 조건

• $2\le N\le150$
• $0\le A[i]\le1$ ($0\le i<N$인 각 $i$에 대해)
• $0\le S[i][0]<N$ 및 $0\le S[i][1]<N$ ($0\le i<N$인 각 $i$에 대해)
• $1\le M\le50\,000$
• $0\le B[j]\le1$ ($0\le j<M$인 각 $j$에 대해)
• $0\le T[j][0]<M$ 및 $0\le T[j][1]<M$ ($0\le j<M$인 각 $j$에 대해)
• $K=N$

서브태스크

1. (21점) $N=2$
2. (30점) $N\le30$이고 $0$부터 $N-1$까지의 각 $i$에 대해 $S[i][0]=S[i][1]$입니다.
3. (20점) $N\le30$이고 $K=N^2$입니다.
4. (29점) 추가 제약 조건이 없습니다.

샘플 그레이더는 다음 형식으로 입력을 읽습니다.

• $1$번째 줄: $N\ K$
• $2+i$번째 줄 ($0\le i<N$): $A[i]\ S[i][0]\ S[i][1]$

샘플 그레이더가 프로토콜 위반을 감지하면 샘플 그레이더의 출력은 Protocol Violation: <MSG>이며, 여기서 <MSG>는 다음 오류 메시지 중 하나입니다.

• missing call: construct_card 프로시저가 define_states를 호출하지 않고 반환했습니다.
• too many calls: construct_card 프로시저가 define_states를 두 번 이상 호출했습니다.
• invalid number: $M$이 $1$ 이상 $50\,000$ 이하의 정수가 아닙니다.
• invalid array: 배열 $B$의 길이 또는 배열 $T$의 길이가 $M$과 다르거나, $T[j]$의 길이가 $2$가 아닌 인덱스 $j$ ($0\le j<M$)가 존재합니다.
• invalid bit: $B[j]$가 $0$ 또는 $1$이 아닌 인덱스 $j$ ($0\le j<M$)가 존재합니다.
• invalid state: $T[j][0]$과 $T[j][1]$ 중 적어도 하나가 $0$ 이상 $M-1$ 이하의 정수가 아닌 인덱스 $j$ ($0\le j<M$)가 존재합니다.
• invalid initial state: j0이 $0$ 이상 $M-1$ 이하의 정수가 아닙니다.

그렇지 않으면 샘플 그레이더는 두 가지 출력을 생성합니다.

먼저, 샘플 그레이더는 만들어진 키카드를 다음 형식으로 출력합니다.

• $1$번째 줄: $M\ \mathtt{j0}$
• $2+j$번째 줄 ($0\le j<M$): $B[j]\ T[j][0]\ T[j][1]$

둘째, 샘플 그레이더는 작업 디렉터리에 lockpicking.bin 파일을 작성합니다. 이 파일은 다음 절에서 설명하는 테스팅 도구의 입력으로 사용됩니다.

테스팅 도구

이 과제의 첨부 패키지에는 display.py라는 파일이 들어 있습니다. 이 Python 스크립트를 실행하면 자물쇠와 키카드 사이의 검증 과정을 시뮬레이션합니다. 이를 위해 바이너리 파일 lockpicking.bin이 작업 디렉터리에 있어야 합니다.

첫 번째 시뮬레이션에서 자물쇠의 초기 상태는 $0$입니다. 시뮬레이션이 완료되면 간단한 그래픽 인터페이스가 나타납니다. 주요 기능은 다음과 같습니다.

• 창 아래쪽에서 검증의 전체 결과(현재 자물쇠 초기 상태에 대한 결과)를 볼 수 있습니다.
• 화살표 버튼을 클릭하거나 해당 단축키를 눌러 과정의 단계들을 탐색할 수 있습니다.
• 자물쇠의 초기 상태를 설정하려면 Init Lock 버튼을 사용하십시오.
• Reload 버튼은 설정 파일 lockpicking.bin을 다시 불러옵니다. lockpicking.bin의 내용이 변경된 경우 유용합니다.

마지막 두 작업은 자동으로 시뮬레이션을 다시 실행하고 GUI를 갱신합니다.

스크립트를 실행하려면 다음 명령을 실행하십시오.

python3 display.py