Secret Message Decoder
Time limit1sMemory limit128 MB
Reconstruct a matrix from a row-major binary string, read its cells in clockwise spiral order to recover 5-bit codes, and decode them back into the original letters and spaces.
- Level
Medium5 of 10
- Topics
- Matrix, Simulation, Implementation
- Solved
- No attempts yet
Problem
A sender wants to hide a message before sending it to a receiver. The sender chooses a matrix with R rows and C columns, then creates a binary string by the following rules.
- The original message contains only uppercase English letters and spaces.
- A space is converted to
0,Ato1,Bto2, ..., andZto26. - Each number is written as a 5-bit binary number.
The bits are written into the matrix in clockwise spiral order, starting from the upper-left cell. If there are still empty cells after all message bits are written, the remaining cells are filled with 0. For instance, if the message is "ACM" and R=4, C=4, then A=00001, C=00011, and M=01101 are written in spiral order, and the last remaining cell is filled with 0.
The sender then reads the matrix in row-major order and sends that binary string. In the case above, the sent string is 0000110100101100.
Given R, C, and the received binary string, restore the original message.
Input
The first line contains the number of test cases T (1 <= T <= 1,000). Each test case is given on one line and contains R, a space, C, a space, and the received message.
1 <= R, C <= 21. The received message consists only of 0 and 1, and its length is always exactly R*C.
Output
For each test case, print the original message before conversion. If the original message ends with spaces, remove all trailing spaces before printing it.