You woke up in the morning, turned on your computer and started reading your
mail. Instead of usual two or three letters there were several dozen new messages.
It was a bad omen. Most probably, something unpleasant had happened. Indeed,
having read a couple of letters, you found out that the nomads had robbed another
caravan going to a neighboring town. The caravan had been following a completely new route,
but nevertheless the nomads had managed to track it down and had laid an ambush.
Either they had a lot more people that it had been assumed or someone from the town
was supplying them with information.
Your meditated on it. It was not that easy to pass information outside the
town. Radiation shields protected the town form the surrounding desert and
didn't transmit radio waves. Automatic surveillance systems had not
fixed anyone or anything attempting to approach the town walls. And of course
nobody had visited the desert alone. Only one variant remained, the fiber-optic
cable used for communication with other towns. You were responsible for all
communication systems in the town, and you decided to carry out your own
You spent a whole day designing filters that would analyze traffic and reveal
suspicious activity. In a week, the filters responded and intercepted a strange
data flow. The content of the message was incomprehensible, but it was not very
hard to track down the source. You informed the authorities and started waiting.
The seizure operation ended up in a failure. The betrayer noticed the
approaching troops, barricaded in his house and started firing. Eventually,
the house was taken by assault in which the betrayer suffered a mortal wound.
When his computer was found, the hard disk had been half formatted already.
You spent a lot of time analyzing the vestiges of the information and found
several interesting fragments. One of them contained the following code.
procedure Encode(string text, int t)
int len = GetLength(text);
int n = 8*t*len;
for i = 1 to len
for j = 0 to 7
for k = 0 to t-1
double sample = ZERO_LEVEL
if (GetBit(text[i], j) == 1)
sample += sin(2*k*PI/t)*AMP
sample += sin(4*k*PI/t)*AMP
sample += Noise()
You decided to decode the intercepted message to learn the information the
betrayer had wanted to pass. Unfortunately, you couldn't find the values
of the constants ZERO_LEVEL and AMP as well as the description of the function
Noise(). But even without that it would be easy to write a decoder.
In the first line you are given the integers n and
t, 0 < n ≤ 10000, 5 ≤ t ≤
1000, n is a multiple of 8·t. Then in one or
several lines there are n real numbers in the range from 0 to 1. The
number are given with at most five fractional digits.
Output a line containing the decoded text. It is known that the text consists
of English letters, punctuation signs, and spaces. It is guaranteed that the
text is decoded uniquely.
0.3 0.8 0.6 0.4 0.2
0.5 0.6 0.3 0.9 0.4
0.4 0.8 0.3 0.8 0.2
0.3 0.6 0.1 0.7 0.2
0.7 0.7 0.1 0.7 0.1
0.5 0.8 0.7 0.3 0.2
0.4 0.8 0.2 0.8 0.2
0.5 0.8 0.3 0.8 0.2
Problem Author: Pavel Atnashev
Problem Source: The 13th Urals Collegiate Programing Championship, April 04, 2009