АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

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

Ограничение времени: 1 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Софья считает число интересным, если его цифры идут в неубывающем порядке. Например, числа 123, 1111 или 888999 – интересные.

Софья заинтересовалась, сколько существует интересных положительных чисел, лежащих в диапазоне от L до R включительно. Это число может оказаться довольно большим для больших L и R, поэтому Софья хочет найти остаток от деления этого числа на 109 + 7.

Требуется написать программу, которая по заданным L и R определяет количество интересных чисел, лежащих в диапазоне от L до R включительно, и выводит остаток от деления этого числа на 109 + 7.

Формат входного файла

Входной файл содержит две строки. Первая строка содержит число L, вторая строка содержит число R (1  L  R  10100).

Формат выходного файла

Выходной файл должен одно целое число – остаток от деления количества интересных чисел, лежащих в диапазоне от L до R включительно, на 109 + 7.

Примеры входных и выходных файлов

Входные данные

Выходные данные

1

100

54

Описание подзадач и системы оценивания

Подзадача 1 (21 балл)

L = 1, R  1000

Баллы за подзадачу начисляются только в случае, если все тесты подзадачи пройдены.

Подзадача 2 (до 22 баллов)

1  L  R  1018

В этой подзадаче 11 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Подзадача 3 (до 24 баллов)

L = 1, R = 10k для некоторого целого k, 2  k  100.

В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (до 33 баллов)

1  L  R  10100

В этой подзадаче 11 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Школьные олимпиады Вологодской области / Региональный этап 2015-16 /
1490. 6 - Гипершашки 1491. 1492. 8 - Гармоническая последовательность
 
время генерации 0.141 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.