- Описание
- Решения
- Разборы
- Кодерун AI β
426. Сумма
Вам дано целое положительное число . Найдите все способы, которым это число можно получить, складывая целые положительные числа.
Для того, чтобы не выводить одинаковые способы много раз, суммы должны обладать следующими свойствами:
- Слагаемые в рамках одного выражения идут в невозрастающем порядке.
- Выражения перечисляются в лексикографическом порядке. Иначе говоря, для любой пары выражений верно, что раньше будет выписано то из них, в котором меньше число на первой несовпадающей позиции. Например,
2 + 1 + 1должно быть выписано раньше, чем2 + 2.
Формат ввода
Во входном файле находится единственное число ( ).
Формат вывода
В выходной файл выведите искомые способы получить число , по одному способу на строку. Каждое выражение должно состоять из целых положительных чисел, разделенных знаком +, окруженным пробелами.
Ограничения
- Ограничение времени
- 2 с
- Ограничение памяти
- 64 МБ
Примеры
Пример 1
Ввод
4
Вывод
1 + 1 + 1 + 1
2 + 1 + 1
2 + 2
3 + 1
4