Вы проснулись утром и первым делом сели за компьютер почитать почту. Вместо обычных двух-трёх писем в почтовом
ящике лежало несколько десятков новых сообщений. Это был дурной знак — скорее всего, произошло что-то
неприятное. И действительно, прочитав пару писем, вы выяснили, что кочевники ограбили очередной корован,
направлявшийся в соседний город. Несмотря на то, что караван шёл по совершенно новому маршруту, кочевники
каким-то образом засекли его и устроили засаду. Либо у них было гораздо больше людей, чем считалось ранее,
либо кто-то из города снабжал их информацией.
Вы задумались. Передать информацию за пределы города не так-то просто. Радиационные щиты, защищавшие город
от окружавшей его радиоактивной пустыни, не пропускали радиоволн. Автоматические системы наблюдения
не зафиксировали попыток приближения к городским стенам. И уж тем более, никто не ходил в пустыню один.
Оставался только один вариант — оптоволоконный кабель, использовавшийся для связи с соседними городами.
Поскольку вы отвечали за все системы связи в городе, вы решили провести собственное расследование.
Целый день вы потратили на разработку фильтров, которые анализировали трафик и выявляли подозрительную
активность. Они сработали через неделю, перехватив странный поток данных. Содержимое послания было непонятно,
но отследить источник не составляло труда. Сообщив в компетентные органы, вы стали ждать.
Операция по задержанию предателя окончилась неудачно. Он заметил приближение служителей закона к своему дому,
забаррикадировался там и открыл огонь. В конечном счёте, спецназ был вынужден брать дом штурмом, во время
которого предатель был смертельно ранен. Когда обнаружили его компьютер, жёсткий диск был отформатирован уже
наполовину.
Вы долго анализировали остатки информации и нашли несколько интересных фрагментов. В одном из них был такой код:
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 г.