P15991 [PA 2026] Matrix Encoding / Kodowanie macierzami

Algosia and Bajtek are very busy. They do not have time to come up with original problems, let alone send each other $1000 \times 1000$ matrices—which is exactly what they had to do during this year’s Informatics Olympiad finals. Algosia wants to pass a positive integer to Bajtek. Unfortunately, as often happens to them recently, between them there is a very advanced computer system. Algosia can input a $10 \times 10$ binary matrix into the computer, and then the system will permute the rows and columns of this matrix and send it to Bajtek. Write a program to help Algosia and Bajtek perform encoding and decoding for $t$ numbers. ### Implementation details **This is an interactive communication problem**. Your program will run as two copies—one for Algosia and one for Bajtek. In each run, the first line of input will contain the word Algosia or Bajtek, indicating which side this copy is responsible for. After receiving its word, the program will immediately receive two integers $n$ and $t$ ($1 \le n \le 3 \cdot 10^{16}$, $1 \le t \le 25$), representing the upper bound of the transmitted number and the number of test cases. Then $t$ interactions follow. At the start of the $i$-th interaction, Algosia receives an integer $n_i$ ($1 \le n_i \le n$). She should print 10 lines to the output, each line containing 10 characters. Each character must be 0 or 1. The system will permute the rows and columns of this matrix and then send it, in the same format, to the input of the Bajtek process. After receiving the matrix, the Bajtek process should print the number $n_i$ encoded by Algosia. After printing the number, the next test case begins. **After each output block, you must flush the output buffer, for example by calling `cout.flush()` or `fflush(stdout)`.** ### Notes - The interaction described below corresponds to the first sample test named kod0a.in. - Both programs are started at the same time. The running time is measured as the real time from the interactor’s start to finish. - Algosia will receive the next number only after Bajtek has decoded the previous one. - After reading $n$ and $t$, Bajtek’s process does not need to block waiting for input. It may perform any computations while Algosia is encoding the first number. In extreme cases, this can speed up the program by up to a factor of two.

See “Implementation details”.

See “Implementation details”.

### Sample interaction | Interactor → Algosia | Algosia → Interactor | Interactor → Bajtek | Bajtek → Interactor | Explanation | |:---|:---|:---|:---|:---| | Algosia | | Bajtek | | The interactor tells the Algosia and Bajtek program copies their identities. | | $20$ $2$ | | $20$ $2$ | | Both sides learn that there will be two test cases, and in each case the maximum number to be transmitted does not exceed $20$. | | $12$ | | | | Algosia receives the number $12$ to be encoded. | | | $\texttt{1110000000}\\\texttt{1000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}$ | | | Algosia sends a matrix encoding the number $12$. | | | | $\texttt{0000000000}\\\texttt{0000100000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0100100001}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}$ | | Bajtek receives the matrix with permuted rows and columns. | | | | | $12$ | Bajtek reports that he decoded the number $12$ from the matrix. | | $11$ | | | | Algosia receives the number $11$ to be encoded. | | | $\texttt{1110000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}$ | | | Algosia sends a matrix encoding the number $11$. | | | | $\texttt{0000000100}\\\texttt{0000000100}\\\texttt{1000000101}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}$ | | Bajtek receives the matrix with permuted rows and columns (possibly in a different way than before). | | | | | $11$ | Bajtek reports that he decoded the number $11$ from the matrix. | ### Scoring The testdata consists of 10 groups. Each group is worth either 0 or 1 point. The limits on $n$ for each group are as follows: | Group | $n \le$ | |------|---------| | 1 | $10^{10}$ | | 2 | $10^{11}$ | | 3 | $10^{12}$ | | 4 | $10^{13}$ | | 5 | $10^{14}$ | | 6 | $10^{15}$ | | 7 | $5 \cdot 10^{15}$ | | 8 | $10^{16}$ | | 9 | $2 \cdot 10^{16}$ | | 10 | $3 \cdot 10^{16}$ | ### Local testing An interactor kodsoc.cpp is provided in the “Files” section. The provided interactor does not permute the matrix before sending it to Bajtek; apart from this difference, it performs exactly the same interaction with the contestant’s programs as the interactor used for judging submissions on SIO. Run it as follows: ```bash python3 kodrun.py [解答] < [测试] ``` Here kodsoc.cpp and o1.h must be in the same folder. The input format accepted by the interactor is described in the comments of the kodsoc.cpp file. You can run python3 kodrun.py -h to learn about other options of the kodrun.py script. ### Fair play rules It is forbidden to communicate between the two programs in any way other than through the interaction process, for example by having one program delay sending an action and letting the other program read the clock. If the jury finds attempts of illegal communication between the programs, the submission may be disqualified; in serious cases, the contestant may be disqualified from the entire contest. Translated by ChatGPT 5