ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Demodulation

Time limit: 1.0 second
Memory limit: 64 MB
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 investigation.
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.


40 5
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
To submit the solution for this problem go to the Problem set: 1704. Demodulation