ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

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 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1704. Демодуляция