Receiving a Fax
InterviewTime limit1sMemory limit128 MB
Decode a run-length-encoded byte stream using control bytes that mark literal or repeated runs, then print the result as hex.
- Level
Easy3 of 10
- Topics
- Simulation, Implementation, Array
- Solved
- No attempts yet
Problem
Fax data is compressed with run-length encoding (RLE). The encoded stream is a sequence of packets, and each packet begins with one control byte.
If the most significant bit of the control byte is 0, the packet is a literal packet. Add 1 to the value stored in the remaining 7 bits; that many bytes immediately follow the control byte and must be copied to the decoded output unchanged. A literal packet can therefore store from 1 to 128 bytes.
If the most significant bit of the control byte is 1, the packet is a run packet. Add 3 to the value stored in the remaining 7 bits; that is the number of times to repeat the next byte. A run packet can therefore represent from 3 to 130 copies of the same byte.
Decode each encoded byte stream and output the original bytes.
Input
The first line contains the number of data sets P (1 <= P <= 1000).
Each data set begins with one integer B (1 <= B <= 5000), the number of encoded bytes. The following lines contain exactly B encoded bytes written in hexadecimal. Each full line contains 80 hexadecimal digits, and the last line for a data set may contain fewer.
Two hexadecimal digits represent one byte. Hexadecimal digits are 0 through 9 and A through F.
Output
For each data set, print several lines.
First print the number of decoded bytes. Then print the decoded bytes as uppercase hexadecimal digits, with 80 hexadecimal digits per full line. The last line for a data set may contain fewer than 80 hexadecimal digits.