배낭 문제 준비하기

문제를 출제할 때 큰 비중을 차지하는 일이 데이터 만들기다. 데이터를 만드는 정해진 방법은 없고, 문제마다 나올 만한 오답을 최대한 떠올린 다음 그 오답을 걸러내는 데이터를 준비해야 한다.

다음 문제를 생각해 보자.

중복이 허용되는 집합 $S = \{a_1, a_2, \dots, a_n\}$이 주어진다. $S$의 부분집합 가운데 모든 원소의 합이 $k$인 것은 몇 개인가? 값이 같은 원소라도 위치가 다르면 서로 다르다고 센다.

제약 조건은 $1 \le n \le 300$, $1 \le k \le 300$이고, $S$의 원소는 모두 $k$ 이하의 자연수다.

이 문제에서 나올 만한 오답을 떠올리다 보니, 답이 정확히 $t$인 데이터에서 $t - 1$을 출력하는 답안이 있었다. 그런 답안을 걸러내려면 자연수 $t$가 주어졌을 때 위 문제의 답이 $t$가 되는 집합 $S$와 자연수 $k$를 구하는 프로그램이 필요하다. 그 프로그램을 대신 작성해라.

조건을 만족하는 데이터는 여러 가지이므로, 출력에 적어 둔 방법으로 만든 데이터 하나만 정답으로 인정한다.

첫째 줄에 자연수 $t$가 주어진다. ($1 \le t \le 10^{18}$)

첫째 줄에 $n$과 $k$를 공백으로 구분해 출력한다. 둘째 줄에 $a_1, a_2, \dots, a_n$을 비내림차순으로, 공백으로 구분해 출력한다. $n$, $k$, $S$는 위 제약 조건을 반드시 만족해야 한다.

데이터는 다음 방법으로만 만든다.

1. $k = 300$으로 둔다.
2. 값이 1인 원소를 60개 넣는다.
3. $r = t$로 두고, $r > 0$인 동안 다음을 반복한다. $0 \le d \le 30$ 범위에서 $\binom{60}{d} \le r$을 만족하는 가장 큰 정수 $d$를 고르고, 값이 $300 - d$인 원소를 하나 넣은 뒤 $r$에서 $\binom{60}{d}$를 뺀다.
4. $n$은 넣은 원소의 총 개수다.

3단계에서 넣은 원소는 각각 합이 300인 부분집합을 $\binom{60}{d}$개 만들고, 합이 300인 부분집합은 3단계에서 넣은 원소를 정확히 하나 포함한다. 그래서 이 데이터의 답은 정확히 $t$가 된다. $t \le 10^{18}$이면 $n$은 242를 넘지 않는다.