Grp

시간 제한5초메모리 제한512 MB

요약

n개 문자로 만든 크기 k 이하의 모든 공집합 아닌 부분집합을, 한 묶음 안의 부분집합들이 서로소이고 크기 합이 k 이하가 되도록 최소 개수의 묶음으로 나눈다.

난이도: 보통10점 중 7점
유형: 백트래킹, 조합론, 비트 연산, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Distribute all non-empty subsets of {a, b, c, . . .} (first n lowercase English letters) of size at most k into as few groups as possible, subject to the following conditions:

each subset must belong to exactly one group;
subsets belonging to the same group must have no common elements;
the total size of subsets belonging to the same group must be at most k

입력

The only line contains two integers n and k (1 ≤ k ≤ n ≤ 17).

출력

Display the smallest number of groups g, followed by g group descriptions.

Group description i must consist of an integer si, followed by si subset descriptions. Each subset description must be a string containing subset elements in any order without spaces.

예제2

예제 1
입력
```
3 2
```
예상 출력
```
5
1 ab
1 ac
1 bc
1 b
2 c a
```
예제 2
입력
```
3 3
```
예상 출력
```
4
1 abc
2 ab c
2 ac b
2 bc a
```