Фибоначчиевы суммы

면접 대비

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

요약

n을 비감소 순서의 피보나치 수 합으로 나타내되 각 수를 k번까지만 쓸 수 있을 때, 가능한 모든 표현을 사전순으로 출력한다.

난이도: 보통10점 중 6점
유형: 백트래킹, 재귀, 조합론, 구현
정답자: 아직 제출이 없습니다

문제

Числа Фибоначчи определяются следующим образом: $F\_1 = 1$ , $F\_2 = 2$ , а для $n > 2$ выполнено $F\_n = F\_{n - 2} + F\_{n - 1}$ . Таким образом, начало последовательности чисел Фибоначчи выглядит так $1, 2, 3, 5, 8, 13, 21, \ldots$ .

Вам заданы числа $n$ и $k$ . Требуется найти все способы представить число $n$ в виде суммы неубывающих чисел Фибоначчи, причем кажое число разрешается использовать не более $k$ раз.

입력

Первая строка ввода содержит число $n$ ( $1 \le n \le 100$ ).

Вторая строка ввода содержит число $k$ ( $1 \le k \le 20$ ).

출력

Выведите все искомые представления, по одному на строке. Разделяйте числа знаком <<+>>, не используйте пробелы.

Разбиения следует упорядочить по первому слагаемому, при равном первом слагаемом --- по второму, при равных первых двух --- по третьему, и так далее.

예제1

예제 1
입력
```
6
2
```
예상 출력
```
1+1+2+2
1+2+3
1+5
3+3
```