시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6683 3669 2654 55.108%

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스 마다 수를 고르는 모든 방법을 출력한다. 이 때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력 1

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

예제 출력 1

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34
W3sicHJvYmxlbV9pZCI6IjY2MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NWNcdWI2MTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNjNVx1Yzc3YyBcdWI4NWNcdWI2MTBcdWIyOTQgezEsIDIsIC4uLiwgNDl9XHVjNWQwXHVjMTFjIFx1YzIxOCZuYnNwOzZcdWFjMWNcdWI5N2MgXHVhY2UwXHViOTc4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI4NWNcdWI2MTAgXHViYzg4XHVkNjM4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWMwYWNcdWM2YTlcdWI0MThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWM4MDRcdWI3YjVcdWM3NDAgNDlcdWFjMDBcdWM5YzAgXHVjMjE4IFx1YzkxMSBrKGsmZ3Q7NilcdWFjMWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YWNlOFx1Yjc3YyBcdWM5ZDFcdWQ1NjkgU1x1Yjk3YyBcdWI5Y2NcdWI0ZTAgXHViMmU0XHVjNzRjIFx1YWRmOCBcdWMyMThcdWI5Y2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBrPTgsIFM9ezEsMiwzLDUsOCwxMywyMSwzNH1cdWM3NzggXHVhY2JkXHVjNmIwIFx1Yzc3NCBcdWM5ZDFcdWQ1NjkgU1x1YzVkMFx1YzExYyBcdWMyMThcdWI5N2MgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWNkMWQgMjhcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuIChbMSwyLDMsNSw4LDEzXSwgWzEsMiwzLDUsOCwyMV0sIFsxLDIsMyw1LDgsMzRdLCBbMSwyLDMsNSwxMywyMV0sIC4uLiwgWzMsNSw4LDEzLDIxLDM0XSk8XC9wPlxyXG5cclxuPHA+XHVjOWQxXHVkNTY5IFNcdWM2NDAga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMyMThcdWI5N2MgXHVhY2UwXHViOTc0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQgayAoNiAmbHQ7IGsgJmx0OyAxMylcdWM3NzRcdWFjZTAsIFx1YjJlNFx1Yzc0YyBrXHVhYzFjIFx1YzIxOFx1YjI5NCBcdWM5ZDFcdWQ1NjkgU1x1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHVjMjE4XHVjNzc0XHViMmU0LiBTXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjI5NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHViMmU0IFx1YzIxOFx1Yjk3YyBcdWFjZTBcdWI5NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YzBhY1x1YzgwNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViZTQ4IFx1YzkwNFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjY2MDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMb3R0byIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIEdlcm1hbiBMb3R0byB5b3UgaGF2ZSB0byBzZWxlY3QgNiBudW1iZXJzIGZyb20gdGhlIHNldCB7MSwyLC4uLiw0OX0uIEEgcG9wdWxhciBzdHJhdGVneSB0byBwbGF5IExvdHRvIC0gYWx0aG91Z2ggaXQgZG9lc24mIzM5O3QgaW5jcmVhc2UgeW91ciBjaGFuY2Ugb2Ygd2lubmluZyAtIGlzIHRvIHNlbGVjdCBhIHN1YnNldCBTIGNvbnRhaW5pbmcgayAoayZndDs2KSBvZiB0aGVzZSA0OSBudW1iZXJzLCBhbmQgdGhlbiBwbGF5IHNldmVyYWwgZ2FtZXMgd2l0aCBjaG9vc2luZyBudW1iZXJzIG9ubHkgZnJvbSBTLiBGb3IgZXhhbXBsZSwgZm9yIGs9OCBhbmQgUyA9IHsxLDIsMyw1LDgsMTMsMjEsMzR9IHRoZXJlIGFyZSAyOCBwb3NzaWJsZSBnYW1lczogWzEsMiwzLDUsOCwxM10sIFsxLDIsMyw1LDgsMjFdLCBbMSwyLDMsNSw4LDM0XSwgWzEsMiwzLDUsMTMsMjFdLCAuLi4gWzMsNSw4LDEzLDIxLDM0XS48XC9wPlxyXG5cclxuPHA+WW91ciBqb2IgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgcmVhZHMgaW4gdGhlIG51bWJlciBrIGFuZCB0aGUgc2V0IFMgYW5kIHRoZW4gcHJpbnRzIGFsbCBwb3NzaWJsZSBnYW1lcyBjaG9vc2luZyBudW1iZXJzIG9ubHkgZnJvbSBTLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGZpbGUgd2lsbCBjb250YWluIG9uZSBvciBtb3JlIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIG9uZSBsaW5lIGNvbnRhaW5pbmcgc2V2ZXJhbCBpbnRlZ2VycyBzZXBhcmF0ZWQgZnJvbSBlYWNoIG90aGVyIGJ5IHNwYWNlcy4gVGhlIGZpcnN0IGludGVnZXIgb24gdGhlIGxpbmUgd2lsbCBiZSB0aGUgbnVtYmVyIGsgKDYgJmx0OyBrICZsdDsgMTMpLiBUaGVuIGsgaW50ZWdlcnMsIHNwZWNpZnlpbmcgdGhlIHNldCBTLCB3aWxsIGZvbGxvdyBpbiBhc2NlbmRpbmcgb3JkZXIuIElucHV0IHdpbGwgYmUgdGVybWluYXRlZCBieSBhIHZhbHVlIG9mIHplcm8gKDApIGZvciBrLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IGFsbCBwb3NzaWJsZSBnYW1lcywgZWFjaCBnYW1lIG9uIG9uZSBsaW5lLiBUaGUgbnVtYmVycyBvZiBlYWNoIGdhbWUgaGF2ZSB0byBiZSBzb3J0ZWQgaW4gYXNjZW5kaW5nIG9yZGVyIGFuZCBzZXBhcmF0ZWQgZnJvbSBlYWNoIG90aGVyIGJ5IGV4YWN0bHkgb25lIHNwYWNlLiBUaGUgZ2FtZXMgdGhlbXNlbHZlcyBoYXZlIHRvIGJlIHNvcnRlZCBsZXhpY29ncmFwaGljYWxseSwgdGhhdCBtZWFucyBzb3J0ZWQgYnkgdGhlIGxvd2VzdCBudW1iZXIgZmlyc3QsIHRoZW4gYnkgdGhlIHNlY29uZCBsb3dlc3QgYW5kIHNvIG9uLCBhcyBkZW1vbnN0cmF0ZWQgaW4gdGhlIHNhbXBsZSBvdXRwdXQgYmVsb3cuIFRoZSB0ZXN0IGNhc2VzIGhhdmUgdG8gYmUgc2VwYXJhdGVkIGZyb20gZWFjaCBvdGhlciBieSBleGFjdGx5IG9uZSBibGFuayBsaW5lLiBEbyBub3QgcHV0IGEgYmxhbmsgbGluZSBhZnRlciB0aGUgbGFzdCB0ZXN0IGNhc2UuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 1996 F번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013