시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 124 | 65 | 61 | 52.586% |
Alice and Bob communicate via a matrix channel. Alice wants to send a message to Bob. She has a bitstring representing her message and performs a bitwise encoding algorithm: She starts with the identity matrix
\[A =\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \]
and then reads the bitstring starting from the left-most bit. For each 0-bit she multiplies the matrix \(A\) from the right with
\[A = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \text{ , i.e. } A \leftarrow A \cdot \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \]
For each 1-bit she multiplies the matrix \(A\) from the right with
\[A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \text{ , i.e. } A \leftarrow A \cdot \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \]
Then the result is transmitted.
Now Bob accidentally deleted the software to decrypt a message from Alice. Can you help him to rewrite it?
The input consists of:
The bitstring representing the message consists of at most 120 characters.
Output the decoded bitstring.
2 1 3 2
010
18 29 13 21
10010101