Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: МАРШРУТЫ

В государстве Чудаков N городов ( 2 <=N <= 16 ), обозначаемых заглавными латинскими буквами, начиная с A, по порядку. Между некоторыми из них проложены дороги, которые могут быть как односторонними, так и двусторонними, причем не обязательно, что из каждого города можно проехать в любой другой.

В государстве всего один маршрут автобуса – 'Ч', который совершает только один рейс каждый день. Выходя из некоторого города, он совершает ровно N переездов между городами так, чтобы вернуться в тот, из которого выехал. Других ограничений на его маршрут нет. В течение дня автобус может несколько раз проезжать один и тот же город или дорогу. В каждом городе существуют автобусные парки, из которых могут выезжать автобусы маршрута 'Ч'. Так что, хотя автобус каждый день возвращается в город, из которого стартовал в этот день, на следующий день начало маршрута 'Ч' может быть из любого другого города. Но рейс каждый день только один.

Маршрут обозначается N буквами, начиная с города, из которого происходит выезд. Например, BCDCE – допустимый маршрут для государства из 5 городов ссоответствующими дорогами: выехать из B, проехать в C, затем в D, вернуться в C, проехать в E и вернуться в изначальный город B (последний пункт маршрута, совпадающий с первым, в маршруте не указывается).

Маршрут автобуса меняется каждый день так, что список маршрутов по дням расположен в словарном порядке и содержит все возможные маршруты. Когда список кончается, его обход начинается сначала. В первый день введения маршрута 'Ч' автобус шёл по первому по порядку маршруту. Выведите его маршрут на день K работы маршрута. Пример: В государстве четыре города: A, B, C, D. Наличие дорог между ними задано матрицей, где элемент равен 1, если из города, соответствующего строке, в город, соответствующий столбцу, есть дорога, и 0 – иначе (на главной диагонали нули – дорог, ведущих назад в тот же город, не бывает).


откуда/куда A B C D
A 0 0 1 1
B 1 0 1 1
C 0 1 0 0
D 0 1 1 0


Полное расписание маршрутов в таком государстве выглядит так:
ADCB
BADC
BCBC
BCBD
BDBC
BDBD
CBAD
CBCB
CBDB
DBCB
DBDB
DCBA

Таким образом, например, маршрут на день 30 – это BDBD.

Формат входных данных
В первой строке указывается количество городов N ( 2<= N <= 16 ). Далее следует N строк по N элементов (цифр), разделенных пробелом, содержащих матрицу, задающую дороги между городами. Далее следует строка содержащая целое число D – номер дня, маршрут которого требуется определить ( 1<= D <= 264 ).

Формат выходных данных
В единственной строке указывается маршрут, т.е. порядок посещения городов, например BDBD (см. предыдущий пример).

Ввод Вывод
3
0 1 1
1 0 1
1 1 0
4
BCA



Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: