images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 20:20:45

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2311. Опасный пролив

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Пиратской шхуне нужно пройти длинный и узкий пролив с многочисленными рифами, ведущий с запада на восток. Так как дует восточный ветер, шхуне приходится идти галсами – двигаться либо на северо-восток, либо на юго-восток, но возле берега пираты, отталкиваясь шестами и веслами, могут двигаться строго на восток. Пираты не могут отталкиваться от рифов, только от берегов. В начальный момент времени шхуна находится возле южного берега пролива и паруса установлены так, что шхуну прижимает к южному берегу и усилиями пиратов она двигается на восток вдоль южного берега. Необходимо провести шхуну на восточный край пролива, не наткнувшись на рифы и сделав минимальное количество изменений направления движения.
Первая строка ввода содержит одно целое число – длину пролива `N` (`1\ ≤\ N\ ≤\ 100000`). Далее следует 10 строк, содержащих по `N` символов '.' (вода) и 'X' (риф) – карта пролива. Гарантируется, что безопасный путь существует.
В первой строке вывести одно целое число – минимальное количество изменений галсов `K`. Во второй строке вывести `K` чисел от 1 до `N` в порядке возрастания – расстояния от западного края пролива, на которых нужно менять галс. Если существует несколько вариантов безопасного пути с минимальным количеством изменений галсов, то вывести любой из них.

Пример ввода

11
.....XX...X
....XX...XX
...XX...XX.
...........
....XXX....
...........
.....X.....
....XX...X.
...XX...XX.
...X...XX..

Пример вывода

3
2 6 8
loading