E. Демодуляция @ Чемпионат Урала 2009 @ Timus Online Judge

E. Демодуляция

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вы проснулись утром и первым делом сели за компьютер почитать почту. Вместо обычных двух-трёх писем в почтовом ящике лежало несколько десятков новых сообщений. Это был дурной знак — скорее всего, произошло что-то неприятное. И действительно, прочитав пару писем, вы выяснили, что кочевники ограбили очередной корован, направлявшийся в соседний город. Несмотря на то, что караван шёл по совершенно новому маршруту, кочевники каким-то образом засекли его и устроили засаду. Либо у них было гораздо больше людей, чем считалось ранее, либо кто-то из города снабжал их информацией.

Вы задумались. Передать информацию за пределы города не так-то просто. Радиационные щиты, защищавшие город от окружавшей его радиоактивной пустыни, не пропускали радиоволн. Автоматические системы наблюдения не зафиксировали попыток приближения к городским стенам. И уж тем более, никто не ходил в пустыню один. Оставался только один вариант — оптоволоконный кабель, использовавшийся для связи с соседними городами. Поскольку вы отвечали за все системы связи в городе, вы решили провести собственное расследование.

Целый день вы потратили на разработку фильтров, которые анализировали трафик и выявляли подозрительную активность. Они сработали через неделю, перехватив странный поток данных. Содержимое послания было непонятно, но отследить источник не составляло труда. Сообщив в компетентные органы, вы стали ждать.

Операция по задержанию предателя окончилась неудачно. Он заметил приближение служителей закона к своему дому, забаррикадировался там и открыл огонь. В конечном счёте, спецназ был вынужден брать дом штурмом, во время которого предатель был смертельно ранен. Когда обнаружили его компьютер, жёсткий диск был отформатирован уже наполовину.

Вы долго анализировали остатки информации и нашли несколько интересных фрагментов. В одном из них был такой код:

procedure Encode(string text, int t)
begin
   int len = GetLength(text);
   int n = 8*t*len;
   Write(n)
   Write(t)
   for i = 1 to len
      for j = 0 to 7
         for k = 0 to t-1
         begin
            double sample = ZERO_LEVEL
            if (GetBit(text[i], j) == 1)
               sample += sin(2*k*PI/t)*AMP
            else
               sample += sin(4*k*PI/t)*AMP
            sample += Noise()
            Write(sample)
         end
end

Вы решили раскодировать перехваченное сообщение, чтобы узнать, какую именно информацию выдал предатель. К сожалению, не удалось найти значения констант ZERO_LEVEL и AMP, а также описания функции Noise(). Но и без этого написать декодер не составит труда.

Исходные данные

В первой строке указаны целые числа n и t, 0 < n ≤ 10000, 5 ≤ t ≤ 1000, n кратно 8·t. Далее в одной или нескольких строках содержится n вещественных чисел в диапазоне от 0 до 1. Числа даны не более чем с пятью знаками после десятичной точки.

Результат

Выведите единственную строку, содержащую раскодированный текст. Известно, что текст состоит из латинских букв, цифр, знаков препинания и пробелов. Гарантируется, что текст раскодируется однозначно.

Пример

исходные данные	результат
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	!

Автор задачи: Павел Атнашев
Источник задачи: XIII чемпионат Урала по спортивному программированию, 4 апреля 2009 г.