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

시간 제한1초메모리 제한1024 MB

요약

n을 서로 다른 증가하는 자연수의 합으로 나타낼 때, 이웃한 세 항에서 가운데 항이 양 끝 항의 평균이 되지 않는 모든 분할을 출력한다.

난이도: 보통10점 중 6점
유형: 백트래킹, 동적 계획법, 재귀
정답자: 아직 제출이 없습니다

문제

Рассмотрим все представления числа $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

예제 1
입력
```
9
```
예상 출력
```
1+2+6
1+8
2+7
3+6
4+5
9
```