07/04/2025 01:14:47

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1896. A + B = C

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

Часто для пробного тура на различных олимпиадах по информатике предлагается задача "A + B", в которой по заданным целым числам

$A$ и

$B$ требуется найти их сумму.

При проведении городской олимпиады по информатике председатель жюри решил сам подготовить тесты для такой задачи. Для этого он использовал свою оригинальную методику, которая заключалась в следующем: сначала готовятся предполагаемые правильные ответы, а затем подбираются входные данные, соответствующие этим ответам.

Пусть председатель жюри выбрал число

$C$ , запись которого состоит из

$n$ десятичных цифр и не начинается с нуля. Теперь он хочет подобрать такие целые положительные числа

$A$ и

$B$ , чтобы их сумма была равна

$C$ , и запись каждого из них также состояла из

$n$ десятичных цифр и не начиналась с нуля. В дополнение к этому председатель жюри старается подобрать такие числа

$A$ и

$B$ , чтобы каждое из них было красивым. Красивым в его понимании является число, запись которого не содержит двух одинаковых подряд идущих цифр. Например, число 1272 считается красивым, а число 1227 — нет.

Требуется написать программу, которая для заданного натурального числа

$C$ вычисляет количество пар красивых положительных чисел

$A$ и

$B$ , сумма которых равна

$C$ . Поскольку количество пар красивых чисел может быть большим, необходимо вывести остаток от деления этого количества на число

$10^9+7$ .

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

Первая строка входного файла содержит одно целое положительное число

$C$ . Число

$C$ не начинается с нуля. Количество цифр в записи числа

$С$ не превышает 10000.

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

Выходной файл должен содержать одно целое число — остаток от деления количества искомых пар красивых чисел

$A$ и

$B$ на число

$10^9+7$ .

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

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

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

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

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

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

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

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

Пояснения к примерам

Число 22 можно представить в виде суммы двузначных чисел тремя способами: 10 + 12, 11 + 11, 12 + 10. Способ 11 + 11 не подходит, поскольку число 11 не является красивым. Следовательно, ответ для числа 22 равен 2.

Число 200 можно представить в виде суммы трехзначных чисел единственным способом: 100 + 100. Этот способ не подходит, поэтому ответ для числа 200 равен 0.

Число 1000 нельзя представить в виде суммы четырехзначных чисел, поэтому ответ для числа 1000 аналогично равен 0.

Система оценивания

Правильные решения для тестов, в которых

$1\ ≤\ C\ ≤\ 999$ (

$1\ ≤\ n\ ≤\ 3$ ), будут оцениваться из 25 баллов.

Правильные решения для тестов, в которых

$1\ ≤\ C\ ≤\ 999\ 999$ (

$1\ ≤\ n\ ≤\ 6$ ), будут оцениваться из 50 баллов.

Несмотря на выделение отдельных групп тестов для различных длин числа

$C$ , на окончательную проверку будут приниматься только решения, правильно работающие для всех тестов из условия задачи.

Источник: региональный этап Всероссийской олимпиады по информатике 2012/2013, http://neerc.ifmo.ru/school/