# [Gold I] Historia bawełny [문제 링크](https://www.acmicpc.net/problem/7935) ## 문제 설명 <p>Początkowo zadanie to miało być o historii bawełny. Muszę Wam jednak szczerze wyznać, że wena twórcza opuściła mnie zupełnie podczas układania do niego treści. Postanowiłem więc zrezygnować z owej historii i nie owijając w bawełnę, podać Wam treść zadania w wersji surowej:</p> <p>Znajdź g-ty leksykograficznie m-elementowy podzbiór zbioru {1, 2, ..., n}.</p> ## 입력 <p>W pierwszej linii wejścia znajduje się liczba naturalna d (1 ≤ d ≤ 100), określająca liczbę testów, których opisy znajdują się w kolejnych liniach.</p> <p>Każdy test składa się z jednej linii, zawierającej liczby całkowite m, n oraz g (1 ≤ m ≤ n ≤ 500, 1 ≤ g). g będzie zawsze poprawną wartością.</p> ## 출력 <p>Dla każdego testu wypisz linię zawierającą posortowany rosnąco g-ty leksykograficznie podzbiór.</p> ## 풀이 앞에서부터 각 자리에서 그 수를 선택했을 때의 조합 수를 비교하여 건너뛸지 그 수를 선택할지 결정하는 문제입니다. ``` Java import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.math.BigInteger; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static BigInteger[][] comb = new BigInteger[501][501]; public static void main(String[] args) throws IOException { for(int i=0;i<=500;i++) { comb[i][0] = comb[i][i] = BigInteger.ONE; for(int j=1;j<i;j++) { comb[i][j] = comb[i][j-1].multiply(new BigInteger(Integer.toString(i-j+1))).divide(new BigInteger(Integer.toString(j))); } } int t = Integer.valueOf(br.readLine()); while(t-->0) { StringTokenizer st = new StringTokenizer(br.readLine()); int m = Integer.valueOf(st.nextToken()); int n = Integer.valueOf(st.nextToken()); BigInteger g = new BigInteger(st.nextToken()); g = g.subtract(BigInteger.ONE); int cur=0, last=1; while(cur<m) { for(int i=last;i<=n;i++) { BigInteger cnt = comb[n-i][m-cur-1]; if(g.compareTo(cnt)>=0) { g = g.subtract(cnt); } else { bw.write(i+" "); last=i+1; cur++; break; } } } bw.write("\n"); } bw.close(); } // end of main } // end of Main ```