НачалоПодразделы
Другие разделы
| 1577. Экономная маршрутизация |
| 1578. Последний урок |
| 1579. Самый тупой |
| 1580. Бутылка на всех |
| 1581. Вирус 10.10.10 |
| 1582. Конфеты с десятичной точкой |
| 1584. Матрёшки АТЭС |
Дата и время
22/12/2024 16:01:22
1583. Марсианская арифметика: декомпозиция
Марсианская арифметика: декомпозиция
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 04/07/2011 | Лето 2011 - дорешивание (02G) |
| 05/07/2011 | Лето 2011 - 2 (G) |
Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Марсианские правила для сложения натуральных чисел отличаются от земных.
- Аргументы записываются в десятичной системе счисления.
- Производится поразрядное сложение цифр справа налево.
- В случае, если сумма цифр превысила 9, разряд переноса не прибавляется к следующему, а вставляется в результат перед текущим разрядом.
Например, сумма `95238\ +\ 276` вычисляется следующим образом:
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
