Задача A. Полное прохождение 2

Автор:А. Усманов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Этим летом у Анастасии было много свободного времени, и она решила пройти все уровни своей любимой компьютерной игры. Для полного прохождения одного уровня требуется пройти все его эпизоды.

Рассмотрим один уровень из игры. Некоторые из эпизодов можно пройти на разную концовку, из-за которой определяется следующий эпизод уровня. При этом некоторые эпизоды являются конечными — у таких нет следующего эпизода. На каждый эпизод, кроме первого — начального, можно попасть ровно из одного другого эпизода.

После прохождения некоторых эпизодов, на них можно будет сохраниться, и в следующий раз продолжить прохождение с начала этих эпизодов. В каждом уровне есть несколько эпизодов с возможностью сохранения, причем в первом эпизоде точно можно сохраняться.

Анастасии стало интересно, какое минимальное количество эпизодов на каждом уровне ей надо пройти для полного прохождения этого уровня.

Формат входного файла

Уровни игры представлены на следующем изображении (черным цветом обозначены уровни, на которых можно сохраняться):

Файл с изображениями уровней можно скачать ЗДЕСЬ.

Формат выходного файла

Для каждого уровня в новой строке выведите одно целое число — минимальное количество эпизодов, которые нужно пройти, для полного прохождения данного уровня.

Описание системы оценивания

В качестве решения принимается текстовый файл, содержащий ответы к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

На каждый тест должен быть дан ответ (иначе есть риск неверной проверки). Если вы не знаете ответ на какой-то тест, то следует написать в выходном файле "0" (без кавычек).

Баллы начисляются пропорционально количеству правильных ответов в выходном файле.

По запросу сообщается количество набранных баллов.

Тесты Баллы Способ проверки
1-2По 6 баллов за тестПроверка осуществляется сразу после отправки решения
3-6По 10 баллов за тестПроверка осуществляется только после окончания олимпиады
7-10По 12 баллов за тестПроверка осуществляется только после окончания олимпиады

Примеры тестов

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

11

6

Пояснение к примерам

В первом примере в первое прохождение можно пройти уровни (1, 3, 6), во второе прохождение — (1, 3, 7), в третье прохождение (1, 2, 4), в четвертое прохождение — (2, 5). Последнее прохождение можно начать со 2-о эпизода, так как он уже был пройден и на нём можно было сохраниться. Всего для полного прохождения пришлось пройти 11 эпизодов.

Разбор

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


0.152s 0.016s 21