시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 27 14 13 56.522%

문제

많은 프로그래밍 언어는 라이브러리 함수를 이용해서 배열의 값을 정렬할 수 있다. 이 함수를 사용해서 정렬을 하려면, less(x,y)와 같은 비교 함수를 작성해야 한다.

less(x,y)는 정렬한 순서에서 x가 y의 앞에 온다면 true를 리턴하는 함수이다. 이러한 함수는 항상 이치에 맞아야 한다. 즉, 서로 다른 두 원소 x와 y에 대해서, less(x,y)와 less(y,x)중 하나만 true가 되어야 한다.

이 문제에서는 수열에서 도치가 발생하지 않은 경우에 정렬되었다고 한다. less(x,y)에 대한 도치란, 크기가 n인 배열 A에서 less(A[j], A[i]) = true (0 ≤ i < j < n)를 만족하는 경우이다. (less(A[i], A[j]) = false와 동등한 의미가 아니다)

안타깝게도 어떤 프로그래머는 이런 비교 함수를 신중하게 작성하지 않는다. 이러한 경우에는 절대로 수열을 정렬할 수 없는 경우가 생길수도 있다.

less함수의 결과가 모두 주어진다. 이 때, 이 함수를 이용해서 정렬했을 때, 도치의 개수를 최소가 되는 순열을 구하는 프로그램을 작성하시오.

입력

각 테스트 케이스의 첫째 줄에는 배열의 크기 n이 주어진다. (1 ≤ n ≤ 18) 배열의 각 원소는 0번부터 n-1번까지 번호가 매겨져 있다. 다음 n개의 줄에는 길이가 n인 이진 문자열이 주어지며, i번째 줄의 j번째 숫자는 less(i,j)의 리턴값을 의미한다. (0은 false, 1은 true를 의미)

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

출력

각 테스트 케이스에 대해서, 주어진 비교 함수로 정렬했을 때, 도치의 개수가 최소가 되는 순열을 출력한다. 그 다음 줄에는 그 순열에서 도치의 개수를 출력한다. 만약, 도치의 개수가 같은 순열이 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다.

예제 입력 1

4
0111
0000
0100
0110
3
011
011
011
6
101010
011010
110110
000000
111010
001010
0

예제 출력 1

0 3 2 1
0
0 1 2
1
0 1 5 2 3 4
5
W3sicHJvYmxlbV9pZCI6IjQ4MDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzMDBcdWNkYTkgXHVjODE1XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI5Y2VcdWM3NDAgXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkIFx1YzViOFx1YzViNFx1YjI5NCBcdWI3N2NcdWM3NzRcdWJlMGNcdWI3ZWNcdWI5YWMgXHVkNTY4XHVjMjE4XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWJjMzBcdWM1ZjRcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YzgxNVx1YjgyY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVkNTY4XHVjMjE4XHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzExYyBcdWM4MTVcdWI4MmNcdWM3NDQgXHVkNTU4XHViODI0XHViYTc0LCBsZXNzKHgseSlcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmU0NFx1YWQ1MCBcdWQ1NjhcdWMyMThcdWI5N2MgXHVjNzkxXHVjMTMxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+bGVzcyh4LHkpXHViMjk0IFx1YzgxNVx1YjgyY1x1ZDU1YyBcdWMyMWNcdWMxMWNcdWM1ZDBcdWMxMWMgeFx1YWMwMCB5XHVjNzU4IFx1YzU1ZVx1YzVkMCBcdWM2MjhcdWIyZTRcdWJhNzQgdHJ1ZVx1Yjk3YyBcdWI5YWNcdWQxMzRcdWQ1NThcdWIyOTQgXHVkNTY4XHVjMjE4XHVjNzc0XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVkNTY4XHVjMjE4XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM3NzRcdWNlNThcdWM1ZDAgXHViOWRlXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWM2ZDBcdWMxOGMgeFx1YzY0MCB5XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgbGVzcyh4LHkpXHVjNjQwIGxlc3MoeSx4KVx1YzkxMSBcdWQ1NThcdWIwOThcdWI5Y2MgdHJ1ZVx1YWMwMCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjXHViMjk0IFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWIzYzRcdWNlNThcdWFjMDAgXHViYzFjXHVjMGRkXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjODE1XHViODJjXHViNDE4XHVjNWM4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gbGVzcyh4LHkpXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIzYzRcdWNlNThcdWI3ODAsIFx1ZDA2Y1x1YWUzMFx1YWMwMCBuXHVjNzc4IFx1YmMzMFx1YzVmNCBBXHVjNWQwXHVjMTFjIGxlc3MoQVtqXSwgQVtpXSkgPSB0cnVlICgwICZsZTsgaSAmbHQ7IGogJmx0OyBuKVx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzc0XHViMmU0LiAobGVzcyhBW2ldLCBBW2pdKSA9IGZhbHNlXHVjNjQwIFx1YjNkOVx1YjRmMVx1ZDU1YyBcdWM3NThcdWJiZjhcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0KTxcL3A+XHJcblxyXG48cD5cdWM1NDhcdWQwYzBcdWFlNWRcdWFjOGNcdWIzYzQgXHVjNWI0XHViNWE0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmEzOFx1YjI5NCBcdWM3NzRcdWI3ZjAgXHViZTQ0XHVhZDUwIFx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWMyZTBcdWM5MTFcdWQ1NThcdWFjOGMgXHVjNzkxXHVjMTMxXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM4MDhcdWIzMDBcdWI4NWMgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzgxNVx1YjgyY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWMwZGRcdWFlMzhcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5sZXNzXHVkNTY4XHVjMjE4XHVjNzU4IFx1YWNiMFx1YWNmY1x1YWMwMCBcdWJhYThcdWI0NTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWM3NzQgXHVkNTY4XHVjMjE4XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM4MTVcdWI4MmNcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWIzYzRcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MThcdWIyOTQgXHVjMjFjXHVjNWY0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMzBcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyAxOCkgXHViYzMwXHVjNWY0XHVjNzU4IFx1YWMwMSBcdWM2ZDBcdWMxOGNcdWIyOTQgMFx1YmM4OFx1YmQ4MFx1ZDEzMCBuLTFcdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjJlNFx1Yzc0YyBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgblx1Yzc3OCBcdWM3NzRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM3NTggalx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgbGVzcyhpLGopXHVjNzU4IFx1YjlhY1x1ZDEzNFx1YWMxMlx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuICgwXHVjNzQwIGZhbHNlLCAxXHVjNzQwIHRydWVcdWI5N2MgXHVjNzU4XHViYmY4KTxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViZTQ0XHVhZDUwIFx1ZDU2OFx1YzIxOFx1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWIzYzRcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MThcdWIyOTQgXHVjMjFjXHVjNWY0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1YzIxY1x1YzVmNFx1YzVkMFx1YzExYyBcdWIzYzRcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWIzYzRcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWMyMWNcdWM1ZjRcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM1NWVcdWMxMWNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0ODAwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQXBwcm94aW1hdGUgU29ydGluZyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gbWFueSBwcm9ncmFtbWluZyBsYW5ndWFnZXMsIGxpYnJhcnkgZnVuY3Rpb25zIGFyZSBwcm92aWRlZCBmb3Igc29ydGluZyBlbGVtZW50cyBpbiBhbiBhcnJheS4gSW4gb3JkZXIgZm9yIHRoZXNlIHNvcnRpbmcgZnVuY3Rpb25zIHRvIHdvcmsgZm9yIGRpZmZlcmVudCB0eXBlcyBvZiBlbGVtZW50cywgdGhlIHVzZXIgc3VwcGxpZXMgYSBjb21wYXJpc29uIGZ1bmN0aW9uIGxlc3MoeCx5KSB3aGljaCByZXR1cm5zIHRydWUgaWYgYW5kIG9ubHkgaWYgeCBjb21lcyBiZWZvcmUgeSBpbiB0aGUgc29ydGVkIG9yZGVyLiBPZiBjb3Vyc2UsIHRoZSBjb21wYXJpc29uIGZ1bmN0aW9uIGhhcyB0byAmIzM5O21ha2Ugc2Vuc2UmIzM5Oy4gRm9yIGV4YW1wbGUsIGZvciBhbnkgdHdvIGRpZmZlcmVudCBlbGVtZW50cyB4IGFuZCB5LCBleGFjdGx5IG9uZSBvZiBsZXNzKHgseSkgYW5kIGxlc3MoeSx4KSBzaG91bGQgYmUgdHJ1ZS4gRm9yIHRoZSBwdXJwb3NlIG9mIHRoaXMgcHJvYmxlbSwgYW4gYXJyYXkgaXMgc29ydGVkIHdoZW4gdGhlcmUgYXJlIG5vIGludmVyc2lvbnMgd2l0aCByZXNwZWN0IHRvIHRoZSBjb21wYXJpc29uIGZ1bmN0aW9uLiBBbiBpbnZlcnNpb24gd2l0aCByZXNwZWN0IHRvIGxlc3MoeCx5KSBpbiBhbiBhcnJheSBBIG9mIHNpemUgbiAoaW5kZXhlZCBmcm9tIDApIGlzIGEgcGFpciBvZiBpbnRlZ2VycyAwICZsZTsgaSAmbHQ7IGogJmx0OyBuIHN1Y2ggdGhhdCBsZXNzKEFbal0sIEFbaV0pID0gdHJ1ZSAobm90ZSB0aGF0IHRoaXMgbWF5IG5vdCBiZSBlcXVpdmFsZW50IHRvIGxlc3MoQVtpXSwgQVtqXSkgPSBmYWxzZSkuPFwvcD5cclxuXHJcbjxwPlVuZm9ydHVuYXRlbHksIHNvbWUgcHJvZ3JhbW1lcnMgYXJlIG5vdCB2ZXJ5IGNhcmVmdWwgaW4gZGVcdWZiMDFuaW5nIHRoZSBjb21wYXJpc29uIGZ1bmN0aW9uLiBJbiBzdWNoIGNhc2VzLCB0aGVyZSBtYXkgYmUgbm8gd2F5IHRvIHNvcnQgdGhlIGVsZW1lbnRzIGluIGFuIGFycmF5IHRvIHNhdGlzZnkgdGhlIGNvbXBhcmlzb24gZnVuY3Rpb24uIFRoZSBiZXN0IHdlIGNhbiBkbyBpcyB0byBwcm9kdWNlIGEgcGVybXV0YXRpb24gbWluaW1pemluZyB0aGUgbnVtYmVyIG9mIGludmVyc2lvbnMgd2l0aCByZXNwZWN0IHRvIHRoZSBnaXZlbiBjb21wYXJpc29uIGZ1bmN0aW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSwgYW4gaW50ZWdlciBuLCAxICZsZTsgbiAmbGU7IDE4LCBpbmRpY2F0aW5nIHRoZSBzaXplIG9mIHRoZSBhcnJheSBpcyBnaXZlbiBvbiBvbmUgbGluZS4gVGhlIGVsZW1lbnRzIGluIHRoZSBhcnJheSBhcmUgbGFiZWxsZWQgMCwgMSwgMiwgLi4uLCBuLTEuIFRoZSBuZXh0IG4gbGluZXMgZWFjaCBjb250YWlucyBhIGJpbmFyeSBzdHJpbmcgb2YgbGVuZ3RoIG4sIHdpdGggdGhlIGogdGggY2hhcmFjdGVyIG9mIHRoZSBpIHRoIGxpbmUgaW5kaWNhdGluZyB0aGUgcmVzdWx0IG9mIHRoZSBjb21wYXJpc29uIGZ1bmN0aW9uIGxlc3MoaSwgaikgKDAgbWVhbnMgZmFsc2UgYW5kIDEgbWVhbnMgdHJ1ZSkuIFRoZSBlbmQgb2YgaW5wdXQgaXMgaW5kaWNhdGVkIGJ5IGEgY2FzZSBpbiB3aGljaCBuID0gMC4gVGhlIGxhc3QgY2FzZSBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBjYXNlLCBvdXRwdXQgdGhlIHBlcm11dGF0aW9uIHRoYXQgaGFzIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgaW52ZXJzaW9ucyB3aXRoIHJlc3BlY3QgdG8gdGhlIGdpdmVuIGNvbXBhcmlzb24gZnVuY3Rpb24uIFRoaXMgaXMgZm9sbG93ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlciBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgaW52ZXJzaW9ucyBpbiB0aGUgcGVybXV0YXRpb24uIElmIHRoZXJlIGFyZSBtdWx0aXBsZSBwZXJtdXRhdGlvbnMgd2l0aCB0aGUgc2FtZSBudW1iZXIgb2YgaW52ZXJzaW9ucywgb3V0cHV0IHRoZSBvbmUgdGhhdCBpcyBsZXhpY29ncmFwaGljYWxseSBzbWFsbGVzdC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=