아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

목화의 역사

시간 제한1초메모리 제한128 MB

요약
n, m, g가 주어질 때 {1,...,n}의 m개 원소 부분집합 중 사전순으로 g번째 부분집합을 출력한다.
난이도

보통10점 중 5점

유형
조합론, 수학, 그리디
정답자
아직 제출이 없습니다

문제

원래 이 문제는 목화의 역사에 관한 이야기로 꾸미려 했지만, 문제를 만드는 동안 창작의 영감이 완전히 사라지고 말았습니다. 그래서 이야기는 접어 두고, 에둘러 말하지 않고 문제를 있는 그대로 제시하겠습니다.

집합 {1,2,…,n}\{1, 2, \ldots, n\}의 모든 mm개 원소 부분집합 중에서, 사전순으로 gg번째인 부분집합을 찾으세요.

각 부분집합은 그 원소들을 오름차순으로 나열한 수열로 나타내며, 두 부분집합의 사전순 비교는 이 수열들을 앞에서부터 원소 단위로 비교하여 결정합니다. 예를 들어 {1,3,4}\{1, 3, 4\}는 {1,3,5}\{1, 3, 5\}보다 앞서고, {1,3,5}\{1, 3, 5\}는 {2,3,4}\{2, 3, 4\}보다 앞섭니다.

입력

첫 번째 줄에 테스트의 개수를 나타내는 자연수 dd (1≤d≤1001 \le d \le 100)가 주어집니다.

이어지는 dd개의 줄에 각 테스트가 한 줄씩 주어지며, 각 줄에는 세 정수 mm, nn, gg가 공백으로 구분되어 주어집니다 (1≤m≤n≤5001 \le m \le n \le 500, 1≤g≤(nm)1 \le g \le \binom{n}{m}). gg는 항상 유효한 값입니다.

출력

각 테스트마다 한 줄에, 사전순으로 gg번째인 mm개 원소 부분집합의 원소들을 오름차순으로 정렬하여 공백으로 구분해 출력하세요.

예제1

  1. 예제 1

    입력
    3
    3 5 4
    3 5 2
    2 2 1
    
    예상 출력
    1 3 4
    1 2 4
    1 2