Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2279. Скрытая угроза
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 02/04/2016 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 4) |
| 10/07/2023 | Лето 2023-7 сложные (E) |
Ограничения: время – 2500ms/5000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
R2-D2 нужно незаметно провести истребитель Люка к имперской крепости.
В начальный момент времени истребитель находится на высоте 1 метр на расстоянии `L` метров от крепости,
расположенной на вершине скалы высотой `H` метров. Истребитель не может взлетать выше высоты `H`, чтобы не
быть обнаруженным, и не может опускаться до нулевой высоты. За каждую единицу времени истребитель
пролетает 1 метр по горизонтали, при этом он может либо сохранить прежнюю высоту полета, либо изменить её на
целое число метров, но не более чем на `K` метров.
R2-D2 хочет определить количество различных возможных маршрутов полета, которые приведут
истребитель из стартовой позиции в крепость. Так как количество может быть велико, ему достаточно получить
остаток от деления результата на `10^9+9`.
Формат ввода
Первая строка ввода содержит три целых числа – расстояние до крепости `L` (`1\ ≤\ L\ ≤\ 10^12`), высота `H` (`1\ ≤\ H\ ≤\ 100`) и
ограничение изменения высоты `K` (`1\ ≤\ K\ ≤\ H`).
Формат вывода
Вывести остаток от деления количества вариантов маршрута на `10^9+9`.
Пример ввода
5 4 2
Пример вывода
108
