Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1494. Как в 4 приема превратить зиллион цифр в одну?
Индукция и другие математические методыЖадные алгоритмы
Олимпиадные задачи на русском языке
| 02/10/2010 | Личное первенство Южного Урала (D) |
| 14/11/2013 | Занятие 9 для продолжающих (D) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (2)
Возьмем последовательность из `n` цифр. На каждом шаге мы можем расставить знаки +
в произвольном месте между цифрами и найти сумму получившегося выражения.
Если сумма состоит из более чем одной цифры, мы можем применить к ней аналогичный прием.
Доказано, что для превращения любой конечной последовательности цифр в одну цифру,
нужно выполнить такое суммирование не более чем 4 раза.
Рассмотрим, как это сделать. На первом шаге мы должны расставить знаки + так, чтобы
сумма была равна числу вида `a00…00"bc"`, то есть содержала бы не более чем три ненулевых цифр.
При этом достаточно разбивать последовательность цифр только на слагаемые из одной или двух цифр.
Сумма трех ненулевых цифр не будет превышать 27, и на следующем шаге мы получим сумму либо из одной
цифры, либо 10 (для `a+b+c=19`), и в этом случае придется выполнить четвертое суммирование.
Напишите программу, которая разбивает последовательность цифр на слагаемые из одной или двух
цифр, сумма которых будет содержать не более чем три ненулевые цифры.
Ввод содержит последовательность из не более чем `10^6` цифр.
Вывести разбиение на слагаемые.
Пример ввода
1234567
Пример вывода
12+34+5+67
