images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
05/12/2025 14:06:00

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

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

printЗадачи

116. Куча мала

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

На столе кучей вывалено 50 счетных палочек (для удобства идентификации все палочки пронумерованы числами от 1 до 50). Брать из кучи можно только по одной палочке и только свободные палочки, на которых не лежат другие палочки. Требуется определить минимальное количество палочек, которые нужно убрать, чтобы освободить палочку с указанным номером. Например, чтобы освободить палочку с номером 3, нужно убрать палочку с номером 5, затем 1, а затем 4 (всего три палочки).
Ввод
Во входном файле содержится несколько строк. В первой строке содержится одно целое число от 1 до 50 – номер палочки, которую нужно освободить. В следующих строках содержится по два целых числа а и b от 1 до 50 через один пробел, означающих, что на палочке с номером a лежит, непосредственно соприкасаясь, палочка c номером b. Конец списка завершается строкой с числами 0 0.
Вывод
В выходной файл вывести минимальное число палочек, которое нужно убрать, чтобы освободить палочку с заданным номером, либо –1, если освободить палочку не удастся

Пример ввода

3
1 5
2 5
3 4
9 3
3 1
0 0

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

3
loading