수 맞추기 게임

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

요약

M과 K가 주어질 때, N이 1부터 M까지인 각 경우에 1번 학생의 승률을 가장 높이는 첫 질문 후보를 구합니다.

난이도: 보통10점 중 7점
유형: 게임 이론, 동적 계획법, 확률
정답자: 아직 제출이 없습니다

문제

$K$ 명의 학생이 선생님이 고른 수를 맞추는 게임을 한다. 게임은 다음과 같이 진행된다.

선생님은 1 이상 $N$ 이하의 무작위 정수 $X$ 를 고른다. 학생들은 $N$ 의 값을 미리 안다.
1번 학생부터 차례대로 한 명씩 1 이상 $N$ 이하의 수 $Y$ 를 골라 질문한다. $X=Y$ 이면 해당 학생이 이긴다. 그렇지 않으면 선생님이 $Y$ 와 $X$ 의 대소 관계를 모든 학생에게 공개한다.
$K$ 번 학생까지 질문을 마치면 다시 1번 학생의 차례로 돌아간다. $X$ 를 맞추는 학생이 나올 때까지 게임을 진행한다.

각 학생은 자신의 승리 확률을 가장 높이는 질문을 한다. 그러한 질문이 여러 개이면 그중에서 균등한 확률로 무작위로 하나를 골라 질문한다. 모든 학생은 이 전략을 사용한다는 사실을 미리 알고 있다.

목표는 1번 학생이 첫 차례에 질문할 수 있는 수의 후보를 찾는 것이다.

양의 정수 $M$ 과 학생 수 $K$ 가 주어졌을 때, $N = 1, 2, \ldots, M$ 각각에 대해 1번 학생이 첫 차례에 질문할 수의 후보를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 양의 정수 $M$ ( $2 \le M \le 200$ )이 주어진다.

두 번째 줄에는 학생의 수 $K$ ( $2 \le K \le 50$ )이 주어진다.

출력

$M$ 개의 줄에 걸쳐 정답을 출력한다. $i$ 번째 줄에는 $N = i$ 인 경우에 1번 학생의 첫 질문으로 가능한 답의 후보들을 오름차순으로 $P_1, P_2, \ldots, P_k$ 라 할 때, $k+1$ 개의 수를 공백을 사이에 두고 $k P_1 P_2 \ldots P_k$ 형식으로 출력한다.

예제2

예제 1
입력
```
4
3
```
예상 출력
```
1 1
2 1 2
3 1 2 3
2 1 4
```

예제 2

입력

15
5

예상 출력

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