시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 420 170 120 45.113%

문제

N, M, K가 주어질 때, A1 ≤ A2 ≤ ... ≤ AN 이고, A1+A2+...+AN = M을 만족하는 수열 중 사전 순으로 K번째 수열을 출력한다. 모든 Ai는 자연수이다.

예를 들어, N=4, M=9, K=3 이었으면,

  • 1 1 1 6
  • 1 1 2 5
  • 1 1 3 4
  • 1 2 2 4
  • 1 2 3 3
  • 2 2 2 3

총 6개가 가능한데 3번째 수열 1 1 3 4이 정답이다.

입력

첫째 줄에 N, M, K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ M ≤ 220, 1 ≤ K ≤ 2147483647)

출력

합이 M인 길이가 N인 수열 중 K번째 수열을 출력한다. 항상 답이 존재 하는 경우만 입력으로 주어진다.

예제 입력

4 9 3

예제 출력

1 1 3 4

힌트

출처

  • 빠진 조건을 찾은 사람: doju