Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2372. Король холма
Поиск в глубину (DFS)Олимпиадные задачи на русском языке
| 28/10/2017 | Очный тур региональных отборочных командных соревнований для школьников (G) |
| 05/07/2021 | Лето 2021-4 (E) |
| 29/06/2022 | Лето 2022-2 (D) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В соревновании "Король холма" один из участников назначается "королём", а остальные участники
по очереди бросают ему вызов и победитель становится новым "королём". Проигравший участник больше в
соревновании не участвует. Победителем соревнований становится последний "король". Петя участвует в
соревновании и хочет узнать, в каком порядке должны происходить схватки, чтобы он стал победителем соревнований.
Первая строка ввода содержит одно целое числа `N` (`1\ ≤\ N\ ≤\ 1000`) — количество участников соревнований.
Участники имеют номера с 0 по `N-1`. Петя имеет номер 0. Далее следует `N` строк, содержащих
по `N` символов – матрица `A`, показывающая итоги схваток участников. Символ 0 в `i`-й строке
и `j`-м столбце матрицы означает, что участник `i` проигрывает схватку против участника `j`; символ 1 —
что участник `i` побеждает участника `j`, символ X находится в позиции `i=j`. Гарантируется, что `A_{i,j}=1-A_{j,i}` для `i\ ≠\ j`.
Вывести `N` целых чисел — начального короля и порядок, в котором происходят схватки остальных
участников с королём. Если существует несколько вариантов, то можно вывести любой из них.
Если ни одного варианта нет, то вывести
сообщение "impossible".
Пример ввода 1
3 X10 0X1 10X
Пример вывода 1
1 2 0
Пример ввода 2
3 X10 0X0 11X
Пример вывода 2
impossible
