Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
19/03/2023 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 8) |
23/03/2023 | Prime Time (разбор, дорешивание) (проводит BOGAT) (F) |
12/07/2023 | Лето 2023-8 сложные (F) |
10/07/2024 | Лето 2024-8 сложные (F) |
29/11/2024 | ICPC Bedolagi (проводит BOGAT) (D) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Профессор зельеделия Эзоп Шарп страдает от бессонницы и вынужден каждый день готовить себе сонное зелье. Сила зелья равна сумме сил добавленных в него ингредиентов и должна быть не меньше L (чтобы заснуть вечером), но и не больше U (чтобы вовремя проснуться утром). К счастью, в кладовой Хогвартса найдутся в изобилии ингредиенты с любой силой от 1 до 105, причем любые 2 разных вида ингредиентов имеют разную силу. Во избежание побочных эффектов от передозировки, один и тот же ингредиент нельзя добавлять в одно зелье более чем дважды. К сожалению, зелья вызывают привыкание: если выпить зелье с тем же составом ещё раз, оно не подействует. Сколько же дней профессор Шарп сможет справляться с бессоницей? Если число слишком большое, достаточно найти остаток от его деления на 109+9.
В единственной строке ввода содержатся два целых числа L и U (1≤L≤U≤105) – минимальная и максимальная сила зелья.
Вывести одно целое число – остаток от деления количества подходящих сонных зелий на 109+9.
Пример ввода
3 4
Пример вывода
6
Пояснение к примеру: Можно составить два зелья силы 3: из одного ингредиента силы 3, либо двух ингредиентов с силами 1 и 2. Также можно составить четыре зелья силы 4 из таких наборов ингредиентов: 4; 1+3; 1+1+2; 2+2. Зелья 1+1+1 и 1+1+1+1 использовать нельзя из-за передозировки ингредиента с силой 1.