시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 22 12 8 61.538%

문제

양의 정수 n이 주어질 때 N을 1부터 n까지의 정수의 집합이라 하자. N의 부분집합의 수열 A1, …, Ak이 아래의 성질을 만족할 때 완전히 다양화되었다고 한다.

a. 각각의 부분집합 Ai가 짝수 개의 원소로 이루어졌다.

b. 임의의 N의 원소 m에 대해 m을 원소로 갖는 Ai가 m개 존재한다.

예를 들어 {1, 2, 3}의 부분집합으로 이뤄진 수열 {1, 3}, {2, 3}, {2, 3}은 완전히 다양화된 수열이다. (수열의 항은 같을 수 있다)

N의 부분집합의 수열 중 완전히 다양화된 수열은 여러 개가 존재하는데, 그 중 가장 짧은 것을 최소라 한다. 위의 예에서는 3이 세 개의 다른 집합에 나타나야 하므로, 위 수열이 최소이다.

정수 n이 주어졌을 때, 완전히 다양화된 수열이 있는가를 판별하고, 있다면 최소의 다양화된 수열을 찾아라.

입력

양의 정수 n(≤ 100)이 한 줄에 하나씩 입력된다. 0이 입력되면 입력을 종료한다.

출력

집합 N에 대해 완전히 다양화된 수열이 없다면 0을 출력하고 다음 줄에 빈 줄을 출력한다.

완전히 다양화된 수열이 있다면, 수열의 길이를 출력하고 다음 줄에 집합을 출력한 뒤 다음 줄에 빈 줄을 출력한다.

각각의 원소는 오름차순으로 출력하여야 하며, 원소들 사이에는 빈 칸을 하나씩 출력한다. 수열의 집합은 사전순으로 출력하여야 한다. 각각의 문제에 대해 답은 여러 개가 있을 수 있다.

예제 입력 1

8
9
11
17
23
0

예제 출력 1

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

0

11
1 3 4 5 6 7 8 9 10 11
2 3 4 5 6 7 8 9 10 11
2 3 4 5 6 7 8 9 10 11
4 5 6 7 8 9 10 11
5 7 8 9 10 11
6 7 8 9 10 11
6 7 8 9 10 11
8 9 10 11
9 11
10 11
10 11

0

23
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
9 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
12 13 14 15 16 17 18 19 20 21 22 23
13 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
16 17 18 19 20 21 22 23
17 19 20 21 22 23
18 19 20 21 22 23
18 19 20 21 22 23
20 21 22 23
21 23
22 23
22 23
W3sicHJvYmxlbV9pZCI6IjI3NzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2NDRcdWM4MDRcdWQ3ODggXHViMmU0XHVjNTkxXHVkNjU0XHViNDFjIFx1YzIxOFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMgTlx1Yzc0NCAxXHViZDgwXHVkMTMwIG5cdWFlNGNcdWM5YzBcdWM3NTggXHVjODE1XHVjMjE4XHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc3NFx1Yjc3YyBcdWQ1NThcdWM3OTAuIE5cdWM3NTggXHViZDgwXHViZDg0XHVjOWQxXHVkNTY5XHVjNzU4IFx1YzIxOFx1YzVmNCBBPHN1Yj4xPFwvc3ViPiwgJmhlbGxpcDssIEE8c3ViPms8XC9zdWI+XHVjNzc0IFx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWMxMzFcdWM5YzhcdWM3NDQgXHViOWNjXHVjODcxXHVkNTYwIFx1YjU0YyBcdWM2NDRcdWM4MDRcdWQ3ODggXHViMmU0XHVjNTkxXHVkNjU0XHViNDE4XHVjNWM4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+YS4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OSBBPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM5ZGRcdWMyMTggXHVhYzFjXHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4NGNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmIuIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBOXHVjNzU4IFx1YzZkMFx1YzE4YyBtXHVjNWQwIFx1YjMwMFx1ZDU3NCBtXHVjNzQ0IFx1YzZkMFx1YzE4Y1x1Yjg1YyBcdWFjMTZcdWIyOTQgQTxzdWI+aTxcL3N1Yj5cdWFjMDAgbVx1YWMxYyBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgezEsIDIsIDN9XHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI5MDRcdWM5YzQgXHVjMjE4XHVjNWY0IHsxLCAzfSwgezIsIDN9LCB7MiwgM31cdWM3NDAgXHVjNjQ0XHVjODA0XHVkNzg4IFx1YjJlNFx1YzU5MVx1ZDY1NFx1YjQxYyBcdWMyMThcdWM1ZjRcdWM3NzRcdWIyZTQuIChcdWMyMThcdWM1ZjRcdWM3NTggXHVkNTZkXHVjNzQwIFx1YWMxOVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0KTxcL3A+XHJcblxyXG48cD5OXHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWMyMThcdWM1ZjQgXHVjOTExIFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWIyZTRcdWM1OTFcdWQ2NTRcdWI0MWMgXHVjMjE4XHVjNWY0XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHViMzcwLCBcdWFkZjggXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjc3YyBcdWQ1NWNcdWIyZTQuIFx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM1ZDBcdWMxMWNcdWIyOTQgM1x1Yzc3NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YjJlNFx1Yjk3OCBcdWM5ZDFcdWQ1NjlcdWM1ZDAgXHViMDk4XHVkMGMwXHViMDk4XHVjNTdjIFx1ZDU1OFx1YmJjMFx1Yjg1YywgXHVjNzA0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWNkNWNcdWMxOGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWIyZTRcdWM1OTFcdWQ2NTRcdWI0MWMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1Yzc4OFx1YjI5NFx1YWMwMFx1Yjk3YyBcdWQzMTBcdWJjYzRcdWQ1NThcdWFjZTAsIFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWNkNWNcdWMxOGNcdWM3NTggXHViMmU0XHVjNTkxXHVkNjU0XHViNDFjIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWNjM2VcdWM1NDRcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IG4oJmxlOyAxMDApXHVjNzc0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gMFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWI0MThcdWJhNzQgXHVjNzg1XHViODI1XHVjNzQ0IFx1Yzg4NVx1YjhjY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM5ZDFcdWQ1NjkgTlx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjNjQ0XHVjODA0XHVkNzg4IFx1YjJlNFx1YzU5MVx1ZDY1NFx1YjQxYyBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgXHViZTQ4IFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzY0NFx1YzgwNFx1ZDc4OCBcdWIyZTRcdWM1OTFcdWQ2NTRcdWI0MWMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjIFx1YjRhNCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwIFx1YmU0OCBcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjNmQwXHVjMThjXHViMjk0IFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWM2ZDBcdWMxOGNcdWI0ZTQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YmU0OCBcdWNlNzhcdWM3NDQgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc0MCBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmIzOFx1YzgxY1x1YzVkMCBcdWIzMDBcdWQ1NzQgXHViMmY1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjc3MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZ1bGx5IERpdmVyc2lmaWVkIFNlcXVlbmNlcyBvZiBTZXRzIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhIHBvc2l0aXZlIGludGVnZXIgbiwgbGV0IE4gYmUgdGhlIHNldCBvZiBpbnRlZ2VycyBmcm9tIDEgdG8gbi4gQSBmaW5pdGUgc2VxdWVuY2UgQTEsICZoZWxsaXA7LCBBayBvZiBzdWJzZXRzIG9mIE4gaXMgZnVsbHkgZGl2ZXJzaWZpZWQgaWY6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+RWFjaCBzdWJzZXQgQWkgaGFzIGFuIGV2ZW4gbnVtYmVyIG9mIGVsZW1lbnRzLjxcL2xpPlxyXG5cdDxsaT5Gb3IgZWFjaCBlbGVtZW50IG0gaW4gTiwgdGhlcmUgYXJlIGV4YWN0bHkgbSBzZXRzIEFpIGluIHRoZSBzZXF1ZW5jZSB3aXRoIG0gYXMgYSBtZW1iZXIuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZSBzZXF1ZW5jZSBvZiBzdWJzZXRzIHsxLDN9LCB7MiwzfSwgezIsM30gaXMgYSBmdWxseSBkaXZlcnNpZmllZCBzZXF1ZW5jZSBvZiBzdWJzZXRzIG9mIHsxLDIsM30uIChOb3RlIHRoYXQgc3Vic2V0cyBpbiB0aGUgc2VxdWVuY2UgbWF5IGJlIHRoZSBzYW1lLik8XC9wPlxyXG5cclxuPHA+QSBmdWxseSBkaXZlcnNpZmllZCBzZXF1ZW5jZSBvZiBzdWJzZXRzIG9mIE4gaXMgbWluaW1hbCBpZiBubyBvdGhlciBmdWxseSBkaXZlcnNpZmllZCBzZXF1ZW5jZSBvZiBzdWJzZXRzIG9mIE4gaGFzIGEgc21hbGxlciBzZXF1ZW5jZSBjb3VudC4gVGhlIGV4YW1wbGUgYWJvdmUgaXMgbWluaW1hbCBzaW5jZSB0aGUgZWxlbWVudCAzIG11c3Qgb2NjdXIgaW4gMyBkaWZmZXJlbnQgc2V0cy48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtLCB3aGljaCwgZ2l2ZW4gYW4gaW50ZWdlciBuLCBkZXRlcm1pbmVzIHdoZXRoZXIgdGhlcmUgaXMgYSBmdWxseSBkaXZlcnNpZmllZCBzZXF1ZW5jZSBvZiBzdWJzZXRzIG9mIHRoZSBjb3JyZXNwb25kaW5nIHNldCBOIGFuZCwgaWYgdGhlcmUgaXMgYSBmdWxseSBkaXZlcnNpZmllZCBzZXF1ZW5jZSwgZmluZHMgYSBtaW5pbWFsIGZ1bGx5IGRpdmVyc2lmaWVkIHNlcXVlbmNlIG9mIHN1YnNldHMgb2YgTi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCB3aWxsIGJlIGEgc2VxdWVuY2Ugb2YgcG9zaXRpdmUgaW50ZWdlcnMgbigmbGU7IDEwMCksIG9uZSBwZXIgbGluZSBmb2xsb3dlZCBieSBhIHplcm8gKDApIChvbiBhbm90aGVyIGxpbmUpIGluZGljYXRpbmcgdGhlIGVuZCBvZiB0aGUgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SWYgdGhlcmUgaXMgbm8gZnVsbHkgZGl2ZXJzaWZpZWQgc2VxdWVuY2Ugb2Ygc3Vic2V0cyBvZiB0aGUgY29ycmVzcG9uZGluZyBzZXQgTiwgb3V0cHV0IGEgMCBvbiBvbmUgbGluZSBmb2xsb3dlZCBieSBhIGJsYW5rIGxpbmUuPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGlzIGEgZnVsbHkgZGl2ZXJzaWZpZWQgc2VxdWVuY2Ugb2Ygc3Vic2V0cyBvZiB0aGUgY29ycmVzcG9uZGluZyBzZXQgTiwgb3V0cHV0IHRoZSBudW1iZXIgb2Ygc2V0cyBpbiB5b3VyIG1pbmltYWwgc2VxdWVuY2Ugb24gb25lIGxpbmUsIGZvbGxvd2VkIGJ5IHRoZSBzZXRzLCBvbmUgcGVyIGxpbmUsIGZvbGxvd2VkIGJ5IGEgYmxhbmsgbGluZS48XC9wPlxyXG5cclxuPHA+VGhlIGVsZW1lbnRzIG9mIGVhY2ggc2V0IHNob3VsZCBiZSBvdXRwdXQgaW4gaW5jcmVhc2luZyBvcmRlciB3aXRoIGEgc2luZ2xlIHNwYWNlIGJldHdlZW4gbnVtYmVycy4gVGhlIHNldHMgb2Ygc2VxdWVuY2VzIHNob3VsZCBiZSBvdXRwdXQgaW4gbGV4aWNvZ3JhcGhpY2FsIG9yZGVyLiBUaGVyZSBtYXkgYmUgbWFueSBwb3NzaWJsZSBzb2x1dGlvbnMgdG8gZWFjaCBwcm9ibGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2003 Greater New York Programming Contest H번