Problem A
Двусторонний ток
Languages
de
en
et
is
ja
lt
lv
no
pl
ru
sv
Фредерик играет с игрушечной железной дорогой, которую он
сам сделал, чем очень гордится. Дорога состоит из
Фредерику поднадоел наворачивающий круги поезд, и он решил добавить к каждому сегменту стрелочную развилку, чтобы устраивать поезду аварии и прочим образом злобно развлекаться. Стрелочные развилки, однако, нужно запитать электричеством, причем им подходит только специальный, двусторонний ток.
По каждому проводу, проложенному вдоль путей, ток может течь в одном направлении – либо по часовой, либо против часовой стрелки, причем Фредерик может выбирать направление на своё усмотрение. Двусторонний ток можно получить, если подвести к сегменту ток и в одном, и в другом направлении (по двум разным проводам).
Таким образом, Фредерику нужно придумать, в какую сторону направить ток по каждому проводу, чтобы каждый сегмент путей был бы покрыт как минимум одним проводом с током, текущим по часовой стрелке, и одним проводом с током, текущим против часовой стрелки. Помоги Фредерику решить эту задачу.
![\includegraphics[width=0.5\textwidth ]{alternatingfig.pdf}](/problems/alternating/file/statement/ru/img-0001.png)
Решение первого примера. Стрелки вокруг железной дороги показывают провода, поставляющие электричество. Направление каждой стрелки соответствует выбранному Фредериком направлению тока (синий и красный цвет подчеркивают разные направления). Обратите внимание, что все стрелки можно развернуть, чтобы получить второе корректное решение: 11010.
Ввод
На первой строке даны два целых числа
На каждой из следующих
Вывод
На единственной строке вывести последовательность символов
длиной
Если решений нет, вывести текст “impossible”.
Ограничения
Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.
Группа |
Очки |
Ограничения |
Дополнительные ограничения |
1 |
13 |
|
|
2 |
20 |
|
|
3 |
22 |
|
|
4 |
19 |
|
Нет проводов с |
5 |
26 |
|
Пример ввода 1 | Пример вывода 1 |
---|---|
10 5 1 5 6 7 5 1 7 2 2 4 |
00101 |
Пример ввода 2 | Пример вывода 2 |
---|---|
10 5 1 4 2 5 4 7 6 10 8 1 |
impossible |
Пример ввода 3 | Пример вывода 3 |
---|---|
5 2 1 5 3 3 |
impossible |
Пример ввода 4 | Пример вывода 4 |
---|---|
5 3 3 3 2 1 4 2 |
101 |