| Автор: | И. Туфанов | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
Поступила информация, что в одной из пещер горной страны спрятано оружие массового поражения, которое до этого долго искали совсем в другом месте. Поиск оружия — дело опасное, поэтому его поручили роботам, а Вам — управление этими роботами.
Пещера, в которой находится оружие, состоит из N площадок, некоторые из которых соединены лазами. По лазам роботы могут проходить в обоих направлениях. Кроме того, пещера имеет интересную структуру: с любой площадки можно пробраться по лазам на любую другую, при чем единственным образом. Это свойство было названо "древовидностью" пещеры.
Количество роботов ограничено — в пещеру можно запустить не больше K штук. Вы находитесь на площадке с номером 1. После запуска каждого робота ему можно давать команды "перейти с текущей площадки на площадку i", причем площадка i должна быть соединена с текущей. Роботы чрезвычайно неповоротливы, вернее, они вообще неповоротливы. Если робот прошел по какому-то лазу, то больше он там пройти не может (однако позже там может пройти другой робот).
В целях поиска оружия Вам было поручено управлять роботами таким образом, чтобы было исследовано наибольшее количество площадок. Площадка считается исследованной, если там побывал хотя бы один робот. Разумеется, первым делом Вы хотите узнать, сколько пещер может быть исследовано при использовании не более чем K роботов. Благо, компьютер под рукой. Теперь вы можете написать программу, отвечающую на этот вопрос.
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|