images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 20:22:23

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

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

printЗадачи

2274. Интересные числа

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

Софья считает число интересным, если его цифры идут в неубывающем порядке. Например, числа 123, 1111 или 888999 – интересные.
Софья заинтересовалась, сколько существует интересных положительных чисел, лежащих в диапазоне от `L` до `R` включительно. Это число может оказаться довольно большим для больших `L` и `R`, поэтому Софья хочет найти остаток от деления этого числа на `10^9\ +\ 7`.
Требуется написать программу, которая по заданным `L` и `R` определяет количество интересных чисел, лежащих в диапазоне от `L` до `R` включительно, и выводит остаток от деления этого числа на `10^9\ +\ 7`.
Формат входного файла
Входной файл содержит две строки. Первая строка содержит число `L`, вторая строка содержит число `R` (`1 ≤ L ≤ R ≤ 10^{100}`).
Формат выходного файла
Выходной файл должен одно целое число – остаток от деления количества интересных чисел, лежащих в диапазоне от `L` до `R` включительно, на `10^9 + 7`.

Пример ввода

1
100

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

54
Описание подзадач и системы оценивания
Подзадача 1 (21 балл)
`L\ =\ 1`, `R ≤ 1000`
Баллы за подзадачу начисляются только в случае, если все тесты подзадачи пройдены.
Подзадача 2 (до 22 баллов)
`1 ≤ L ≤ R ≤ 10^{18}`
В этой подзадаче 11 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.
Подзадача 3 (до 24 баллов)
`L\ =\ 1`, `R\ =\ 10^k` для некоторого целого `k`, `2\ ≤ k ≤ 100`.
В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
Подзадача 4 (до 33 баллов)
`1 ≤ L ≤ R ≤ 10^{100}`
В этой подзадаче 11 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
Источник: региональный этап Всероссийской олимпиады по информатике 2015/2016, http://neerc.ifmo.ru/school/
loading