Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1583. Марсианская арифметика: декомпозиция
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 04/07/2011 | Лето 2011 - дорешивание (02G) |
| 05/07/2011 | Лето 2011 - 2 (G) |
Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Марсианские правила для сложения натуральных чисел отличаются от земных.
- Аргументы записываются в десятичной системе счисления.
- Производится поразрядное сложение цифр справа налево.
- В случае, если сумма цифр превысила 9, разряд переноса не прибавляется к следующему, а вставляется в результат перед текущим разрядом.
Например, сумма 95238 вычисляется следующим образом:
9 5 2 3 8
2 7 6
9 5 41014
Дано марсианское число A, требуется написать программу,
вычисляющую количество способов разложить A на два неотрицательных слагаемых.
Разложения, отличающиеся порядком различных слагаемых, считаются различными.
Входной файл содержит единственное число – A (0\ ≤\ A\ ≤\ 10^1000).
Выходной файл должен содержать единственное число –
количество способов разложить число A на два слагаемых по модулю 10^8\ +\ 7.
(Иными словами, поскольку ответ может быть большим,
следует вывести остаток от его деления на 10^8\ +\ 7).
Пример ввода 1
23
Пример вывода 1
12
Пример ввода 2
123
Пример вывода 2
52
