Gfgfgfgf

ACM Contest Problems Archive

University of Valladolid (SPAIN)

213 Message Decoding
Some message encoding schemes require that an encoded message be sent in two parts. The rst part, called theheader, contains the characters of the message. The second part contains a pattern that represents the message. You must write a program that can decode messages under such a scheme. The heart of theencoding scheme for your program is a sequence of \key" strings of 0's and 1's as follows: 0; 00; 01; 10; 000; 001; 010; 011; 100; 101; 110; 0000; 0001; : : : ; 1011; 1110; 00000; : : : The rst key inthe sequence is of length 1, the next 3 are of length 2, the next 7 of length 3, the next 15 of length 4, etc. If two adjacent keys have the same length, the second can be obtained from the rst byadding 1 (base 2). Notice that there are no keys in the sequence that consist only of 1's. The keys are mapped to the characters in the header in order. That is, the rst key (0) is mapped to the rstcharacter in the header, the second key (00) to the second character in the header, the kth key is mapped to the kth character in the header. For example, suppose the header is: AB#TANCnrtXc Then 0 ismapped to A, 00 to B, 01 to #, 10 to T, 000 to A, ..., 110 to X, and 0000 to c. The encoded message contains only 0's and 1's and possibly carriage returns, which are to be ignored. The message isdivided into segments. The rst 3 digits of a segment give the binary representation of the length of the keys in the segment. For example, if the rst 3 digits are 010, then the remainder of the segmentconsists of keys of length 2 (00, 01, or 10). The end of the segment is a string of 1's which is the same length as the length of the keys in the segment. So a segment of keys of length 2 is terminatedby 11. The entire encoded message is terminated by 000 (which would signify a segment in which the keys have length 0). The message is decoded by translating the keys in the segments one-at-a-time...