Хаотические разбиения

Задача
Разбор задачи

Рассмотрим все представления числа $$$n$$$ в виде суммы различных целых возрастающих слагаемых: $$$n = a_1 + a_2 + \ldots + a_k$$$, $$$a_1 < a_2 < \ldots < a_k$$$.

Будем называть такое разбиение хаотическим, если для него выполнено следующее условие: для любых трех подряд идущих слагаемых среднее не равно среднему арифметическому крайних. Иначе говоря, для всех $$$i$$$ от 1 до $$$k - 2$$$ выполнено $$$a_{i+1} \ne (a_i + a_{i+2}) / 2$$$.

Задано число $$$n$$$. Выведите все его хаотические разбиения на слагаемые.

Входные данные

На ввод подается целое число $$$n$$$ ($$$1 \le n \le 80$$$).

Выходные данные

Выведите все хаотические разбиения на слагаемые числа $$$n$$$. Разбиения можно выводить в любом порядке. Выводите слагаемые в каждом разбиении, разделяя их знаком «+» без пробелов.

Пример

Входные данные

Выходные данные

1+2+6
1+8
2+7
3+6
4+5
9

Научимся сначала генерировать все возможные разбиения рекурсивным перебором.

Перебираем очередное слагаемое в возрастающем порядке, ставим очередное слагаемое строго больше, чем предыдущее.

Чтобы оставить только хаотические, не ставим, чтобы предпоследнее слагаемое стало равно полусумме соседей.

a[i - 1] != (a[i - 2] + a[i]) / 2
2 * a[i - 1] != a[i - 2] + a[i]
a[i] != 2 * a[i - 1] - a[i - 2]

И получаем следующий код.

def search(n, prefix=[], x=0, y=0):
    if n == 0:
        return print(*prefix, sep='+')
    for z in range((y + 1) if y else 1, n + 1):
        if x and x + z == 2 * y:
            continue
        search(n - z, prefix + [z], y, z)


n = int(input())
search(n)

Хаотические разбиения

Для отправки решения задачи необходимо авторизоваться!