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

printЗадачи

1494. Как в 4 приема превратить зиллион цифр в одну?

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

Возьмем последовательность из `n` цифр. На каждом шаге мы можем расставить знаки + в произвольном месте между цифрами и найти сумму получившегося выражения. Если сумма состоит из более чем одной цифры, мы можем применить к ней аналогичный прием. Доказано, что для превращения любой конечной последовательности цифр в одну цифру, нужно выполнить такое суммирование не более чем 4 раза.
Рассмотрим, как это сделать. На первом шаге мы должны расставить знаки + так, чтобы сумма была равна числу вида `a00…00"bc"`, то есть содержала бы не более чем три ненулевых цифр. При этом достаточно разбивать последовательность цифр только на слагаемые из одной или двух цифр. Сумма трех ненулевых цифр не будет превышать 27, и на следующем шаге мы получим сумму либо из одной цифры, либо 10 (для `a+b+c=19`), и в этом случае придется выполнить четвертое суммирование.
Напишите программу, которая разбивает последовательность цифр на слагаемые из одной или двух цифр, сумма которых будет содержать не более чем три ненулевые цифры.
Ввод содержит последовательность из не более чем `10^6` цифр.
Вывести разбиение на слагаемые.

Пример ввода

1234567

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

12+34+5+67
loading