| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 3 | 2 | 2 | 66.667% |
The Hungarian State Treasury replaced the locking mechanism on one of their safes. This new lock can only be opened by custom keycards. The verification of a keycard follows a special protocol.
The lock has $N$ internal states numbered from $0$ to $N - 1$. For each $i$ from $0$ to $N - 1$, inclusive, there is a bit $A[i]$ and there are two states $S[i][0]$ and $S[i][1]$ associated with state $i$. A bit is a binary digit that is either $0$ or $1$. States $S[i][0]$ and $S[i][1]$ may coincide, and a state may be associated with itself.
Similarly to this, a keycard has $M$ states numbered from $0$ to $M - 1$, and for each $j$ from $0$ to $M - 1$, bit $B[j]$ and states $T[j][0]$ and $T[j][1]$ are associated with state $j$. Hereafter, lock states and keycard states are both referred to as states.
In the verification process, the lock gets paired up with a keycard. Both of them are capable of outputting bits, as well as reading bits from the output of the other. At the start of the process, the lock sets to a specific initial state $i_0$. The keycard also sets to initial state $j_0$, specific to the keycard. They repeat the following steps at most $10^7$ times:
If, at any point over the verification process, the number of errors reaches $K$, the verification fails, and the process terminates. Otherwise, if they complete $10^7$ iterations without registering at least $K$ errors, the verification succeeds, and the lock opens.
Upon setting up the new lock, the mechanics made a mistake: they forgot to specify state $i_0$, the initial state used in the verification process. As a result, whenever the lock gets paired up with a keycard, it is set to an arbitrary (unknown) initial state.
Your task is to construct a keycard capable of opening the lock despite the mistake.
You should implement the following procedure.
void construct_card(int N, int[] A, int[][] S)
This procedure must call the following procedure exactly once to construct a keycard:
void define_states(int M, int[] B, int[][] T, int j0)
construct_card.Constraints on the parameters of define_states are given in the Constraints section below.
Consider a lock that has $N = 2$ states. Bit $A[0] = 0$ and states $S[0][0] = 1$ and $S[0][1] = 0$ are associated with state $0$, and bit $A[1] = 1$ and states $S[1][0] = 1$ and $S[1][1] = 0$ are associated with state $1$. For this example, suppose that the value of $K$ is $2$.
The procedure construct_card is called the following way.
construct_card(2, [0, 1], [[1, 0], [1, 0]])
First, consider a keycard with $M = 1$ state where $B[0] = 1$, $T[0][0] = T[0][1] = 0$ and the initial state is $j_0 = 0$.
In the case when the unknown initial state of the lock is $1$, the steps of the verification process are shown in the following table. The states of the lock and the keycard are denoted by $i$ and $j$, respectively.
| Step | $i$ | $A[i]$ | $j$ | $B[j]$ | Errors so far | $S[i][B[j]]$ | $T[j][A[i]]$ |
|---|---|---|---|---|---|---|---|
| $0$ | $1$ | $1$ | $0$ | $1$ | $0$ | $S[1][1] = 0$ | $T[0][1] = 0$ |
| $1$ | $0$ | $0$ | $0$ | $1$ | $1$ | $S[0][1] = 0$ | $T[0][0] = 0$ |
| $2$ | $0$ | $0$ | $0$ | $1$ | $2$ | $S[0][1] = 0$ | $T[0][0] = 0$ |
Note that the last two columns show the state of the lock and the keycard for the next step.
We see that there is no error in step $0$ as we have $A[i] = B[j]$. Following step $0$, there is an error in step $1$, as well as in step $2$, so the verification fails, and the process terminates. Therefore, this keycard is not capable of opening the lock.
Consider a keycard with $M = 2$ states and suppose that $B = [0, 1]$ and $T = [[1, 1],[0, 0]]$ and the initial state is $j_0 = 0$.
If the initial state of the lock is $0$, the verification goes as follows.
| Step | $i$ | $A[i]$ | $j$ | $B[j]$ | Errors so far | $S[i][B[j]]$ | $T[j][A[i]]$ |
|---|---|---|---|---|---|---|---|
| $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $S[0][0] = 1$ | $T[0][0] = 1$ |
| $1$ | $1$ | $1$ | $1$ | $1$ | $0$ | $S[1][1] = 0$ | $T[1][1] = 0$ |
| $2$ | $0$ | $0$ | $0$ | $0$ | $0$ | $S[0][0] = 1$ | $T[0][0] = 1$ |
At this point, we may deduce that the verification process will succeed without errors.
If the initial state of the lock is $0$, the verification goes as follows.
| Step | $i$ | $A[i]$ | $j$ | $B[j]$ | Errors so far | $S[i][B[j]]$ | $T[j][A[i]]$ |
|---|---|---|---|---|---|---|---|
| $0$ | $1$ | $1$ | $0$ | $0$ | $1$ | $S[1][0] = 1$ | $T[0][1] = 1$ |
| $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $S[1][1] = 0$ | $T[1][1] = 0$ |
| $2$ | $0$ | $0$ | $0$ | $0$ | $1$ | $S[0][0] = 1$ | $T[0][0] = 1$ |
At this point, we may deduce that the verification process will succeed without additional errors.
Therefore, this keycard can open the lock irrespective of its initial state. The procedure may call define_states in the following way.
define_states(2, [0, 1], [[1, 1], [0, 0]], 0)
After define_states completes, procedure construct_card should return.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 21 | $N = 2$ |
| 2 | 30 | $N ≤ 30$ and $S[i][0] = S[i][1]$ for each $i$ from $0$ to $N - 1$, inclusive. |
| 3 | 20 | $N ≤ 30$ and $K = N^2$ |
| 4 | 29 | No additional constraints. |
The sample grader reads the input in the following format:
If the sample grader detects a protocol violation, the output of the sample grader is Protocol Violation: <MSG>, where <MSG> is one of the error messages:
missing call: the procedure construct_card returned without making a call to define_states.too many calls: the procedure construct_card made more than one call to define_states.invalid number: $M$ is not an integer between $1$ and $50\,000$.invalid array: the length of array $B$ or the length of array $T$ is different from $M$, or there exists an index $j$ ($0 ≤ j < M$) such that the length of $T[j]$ is not $2$.invalid bit: there exists an index $j$ ($0 ≤ j < M$) such that $B[j]$ is not $0$ or $1$.invalid state: there exists an index $j$ ($0 ≤ j < M$) such that at least one of $T[j][0]$ and $T[j][1]$ is not an integer between $0$ and $M - 1$.invalid initial state: $j0$ is not an integer between $0$ and $M - 1$.Otherwise, the sample grader produces two outputs.
First, the sample grader prints the constructed keycard in the following format:
Second, the sample grader writes a file lockpicking.bin in the working directory. This file serves as the input of the testing tool described in the following section.
The attachment package for this task contains a file named display.py. When invoked, this Python script simulates the verification process between a lock and a keycard. For this, the binary file lockpicking.bin must be present in the working directory.
The initial state of the lock is $0$ in the first simulation. After the simulation completes, a simple graphical interface shows up. The main features are as follows.
Init Lock button.Reload button reloads the configuration file lockpicking.bin. It is useful if the contents of lockpicking.bin have changed.The last two operations automatically rerun the simulation and update the GUI.
To invoke the script, execute the following command.
python3 display.py
C++17, C++20, C++17 (Clang), C++20 (Clang)