Hello space!

Ученые из центра космических наблюдений зафиксировали полезный информационный сигнал, который поступает из далекой галактики. Оказалось, что информацию передают некоторые разумные существа, посылая в сторону Земли луч, яркость которого изменяется с обычной на повышенную, и наоборот. Если информация не передается, то яркость луча обычная и не меняется во времени (пустой сигнал).

Ученым удалось распознать правило, по которому инопланетяне кодируют полезный сигнал. Он является двоичным кодом, причем в течение сеанса связи передача каждого бита сигнала занимает одно и то же вещественное время T. Для передачи бита “1” яркость луча в течение времени T/2 повышенная, а в течение второй половины времени T/2 – обычная. Передача бита “0” осуществляется наоборот: в течение первой половины времени T/2 яркость луча обычная, а в течение второй половины времени T/2 – повышенная. Ученые считают, что первый бит полезного сигнала всегда равен единице, а последний бит – нулю. Для наглядности пример передачи каждого из битов представлен на рисунке:

Ученым удалось сконструировать прибор, который позволяет представить информацию, поступающую из далекой галактики, в виде последовательности нечетной длины, состоящей из целых чисел, определяющих, сколько времени передающий луч находился в постоянном состоянии. Первое число этой последовательности показывает время, в течение которого луч находился в состоянии повышенной яркости, второе число – в состоянии обычной яркости, третье – снова повышенной яркости и т.д. Последнее число последовательности (как и первое) показывает время нахождения луча в состоянии повышенной яркости.

К сожалению, построенный прибор не является абсолютно точным – результаты всех измерений, которые он производит, имеют относительную погрешность, не превосходящую 10%. Это значит, что реальное время , в течение которого луч находился в постоянном состоянии (L – вещественное число), и зафиксированное прибором время (L' – целое число) удовлетворяют неравенству |L - L'| / L ≤ 0.1 .

В качестве примера рассмотрим передачу сигнала “110”, если T = 84.6.

При точной работе прибор зафиксировал бы следующую последовательность:

42.3, 42.3, 42.3, 84.6, 42.3

Обратите внимание, что данная последовательность не зависит от момента времени, в который началась передача сигнала.

Однако из-за наличия погрешности результат работы прибора достаточно непредсказуем. К примеру, полученная последовательность может быть следующего вида:

42, 43, 39, 93, 44

Ученым при помощи построенного прибора удалось получить информацию о K инопланетных сигналах. Теперь задача состоит в том, чтобы по полученной прибором информации определить сами сигналы. Эта задача осложняется тем, что ученые не знают, какое значение T инопланетяне использовали для передачи сигналов. Более того, для передачи разных сигналов могли использоваться разные значения T. Вам как начальнику отдела инновационных технологий центра космических наблюдений была поручена разработка программы для решения этой задачи.

Входные данные

В первой строке входного файла INPUT.TXT записано целое число K – количество принятых инопланетных сигналов (1 ≤ K ≤ 5). Далее следует описание K сигналов. Описание каждого сигнала начинается со строки, содержащей целое нечетное число N – длина последовательности, которую зафиксировал прибор для данного сигнала (3 ≤ N ≤ 32767). Далее следует N строк, в каждой из которых записано одно целое число T_i – значение i-го элемента последовательности (0 < T_i ≤ 10⁹).

Выходные данные

В выходной файл OUTPUT.TXT для каждого из сигналов необходимо вывести одну строку из N символов '0'/'1' – двоичный код принятого сигнала. Если существует несколько способов восстановления сигнала, то выведите любой из них. Если не существует ни одного способа восстановления сигнала, то выведите строку "ERROR".

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]