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

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

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

printЗадачи

1537. Доставка посылки

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

14133.jpg14132.jpg
чередную посылку команде “Планетарной экспресс-доставки” пришлось доставлять на планету Хичкок, сплошь покрытую острыми скалами. Корабль приземлился на небольшом плато немного в стороне от почтового ящика. Путь между кораблем и ящиком пролегал по вершинам острых скал, и опасную миссию по доставке посылки большинством голосов (Лила и Фрай – за, Бендер – против) поручили Бендеру. Бендер должен допрыгать по вершинам скал до почтового ящика и вернуться обратно. Так же, как и Фрай, Бендер всегда стремится минимизировать свои усилия при выполнении любой работы, поэтому требуется найти способ сделать это за минимальное количество прыжков. Бендер может с большой точностью регулировать угол (направление) прыжка, но механизм регулировки силы прыжка из-за проглоченных накануне часов Лилы не работает. Таким образом, начальная скорость Бендера в момент прыжка всегда постоянна и равна `V` м/с. Ускорение свободного падения на планете Хичкок равно 10 м/с`^2`, а сопротивлением воздуха можно пренебречь. Прыжок со скалы на скалу считается успешно выполненным, только если траектория полета приводит Бендера точно на вершину скалы, и он не сталкивается в полете с другими скалами, иначе Бендер может разбиться или застрять между двумя скалами. Напишите программу, которая рассчитает путь Бендера до ящика и обратно.
Во входном файле в первой строке содержатся два целых числа, разделенных пробелом – количество скал `N` и скорость `V` (`2\ ≤\ N\ ≤\ 1000`, `1\ ≤\ V\ ≤\ 100`). Далее следует `N` строк с параметрами скал, по два целых числа в строке – расстояние от скалы до корабля `X_i` в метрах и высота скалы `H_i` в метрах (`0\ =\ X_1\ <\ X_2\ <\ …\ <\ X_N\ ≤\ 100000`, `10\ ≤\ H_i\ ≤\ 10000`, `1\ ≤\ i\ ≤\ N`). Бендер находится на первой скале, а почтовый ящик на `N`-й.
В выходной файл в первой строке вывести минимальное количество прыжков, необходимое для выполнения миссии, а во второй строке – номера скал, на которые совершаются прыжки, разделенные одним пробелом. Если существует несколько вариантов, то вывести один (любой) из них. Если выполнение миссии невозможно, то вывести в первой строке сообщение "MISSION IMPOSSIBLE" (без кавычек).

Пример ввода

6 30
0 100
10 80
40 120
55 90
70 110
95 100

Вывод для примера

4
3 6 5 1
loading