Задача №2517. Следующее разбиение на слагаемые
Разбиения числа \(n\) на слагаемые — это набор целых положительных чисел, сумма которых равна \(n\). При этом разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми, поэтому можно считать, что слагаемые в разбиении упорядочены по неубыванию.
Например, существует 7 разбиений числа 5 на слагаемые:
|
5 = 1 + 1 + 1 + 1 + 1 5 = 1 + 1 + 1 + 2 5 = 1 + 1 + 3 5 = 1 + 2 + 2 5 = 1 + 4 5 = 2 + 3 5 = 5 |
В приведенном примере разбиения упорядочены лексикографически — сначала по первому слагаемому в разбиении, затем по второму, и так далее. В этой задаче вам потребуется по заданному разбиению на слагаемые найти следующее в лексикографическом порядке разбиение.
Входной файл содержит одну строку — разбиение числа \(n\) на слагаемые (\(1 \le n \le 100 000\)). Слагаемые в разбиении следуют в неубывающем порядке.
Выведите в выходной файл одну строку — разбиение числа \(n\) на слагаемые, следующее в лексикографическом порядке после приведенного во входном файле. Если во входном файле приведено последнее разбиение числа \(n\) на слагаемые, выведите «No solution».
5=1+1+3
5=1+2+2
5=5
No solution