Sequence
InterviewTime limit2sMemory limit128 MB
Find the K-th lexicographically smallest non-decreasing sequence of N positive integers summing to M.
- Level
Medium5 of 10
- Topics
- Backtracking, Combinatorics, Recursion
- Solved
- No attempts yet
Problem
Given integers N, M, and K, consider every length-N sequence of positive integers A1, A2, ..., AN that satisfies both conditions below.
- A1 <= A2 <= ... <= AN
- A1 + A2 + ... + AN = M
Sort all such sequences in lexicographic order. Print the K-th sequence. The input is guaranteed to have an answer.
Input
The first line contains three integers N, M, and K. (1 <= N <= 10, 1 <= M <= 220, 1 <= K <= 2147483647)
Output
Print the K-th sequence among all length-N sequences whose sum is M, in lexicographic order. Separate adjacent numbers with a single space.