시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5sZXNzXHVkNTY4XHVjMjE4XHVjNzU4IFx1YWNiMFx1YWNmY1x1YWMwMCBcdWJhYThcdWI0NTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1Yzc3NCBcdWQ1NjhcdWMyMThcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzgxNVx1YjgyY1x1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YjNjNFx1Y2U1OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDE4KSBcdWJjMzBcdWM1ZjRcdWM3NTggXHVhYzAxIFx1YzZkMFx1YzE4Y1x1YjI5NCAwXHViYzg4XHViZDgwXHVkMTMwIG4tMVx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBuXHVjNzc4IFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc1OCBqXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBsZXNzKGksailcdWM3NTggXHViOWFjXHVkMTM0XHVhYzEyXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gKDBcdWM3NDAgZmFsc2UsIDFcdWM3NDAgdHJ1ZVx1Yjk3YyBcdWM3NThcdWJiZjgpPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzhmY1x1YzViNFx1YzljNCBcdWJlNDRcdWFkNTAgXHVkNTY4XHVjMjE4XHViODVjIFx1YzgxNVx1YjgyY1x1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YjNjNFx1Y2U1OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkZjggXHVjMjFjXHVjNWY0XHVjNWQwXHVjMTFjIFx1YjNjNFx1Y2U1OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YjNjNFx1Y2U1OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YzIxY1x1YzVmNFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM4MDQgXHVjMjFjXHVjNzNjXHViODVjIFx1YzU1ZVx1YzExY1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDgwMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFwcHJveGltYXRlIFNvcnRpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkluIG1hbnkgcHJvZ3JhbW1pbmcgbGFuZ3VhZ2VzLCBsaWJyYXJ5IGZ1bmN0aW9ucyBhcmUgcHJvdmlkZWQgZm9yIHNvcnRpbmcgZWxlbWVudHMgaW4gYW4gYXJyYXkuIEluIG9yZGVyIGZvciB0aGVzZSBzb3J0aW5nIGZ1bmN0aW9ucyB0byB3b3JrIGZvciBkaWZmZXJlbnQgdHlwZXMgb2YgZWxlbWVudHMsIHRoZSB1c2VyIHN1cHBsaWVzIGEgY29tcGFyaXNvbiBmdW5jdGlvbiBsZXNzKHgseSkgd2hpY2ggcmV0dXJucyB0cnVlIGlmIGFuZCBvbmx5IGlmIHggY29tZXMgYmVmb3JlIHkgaW4gdGhlIHNvcnRlZCBvcmRlci4gT2YgY291cnNlLCB0aGUgY29tcGFyaXNvbiBmdW5jdGlvbiBoYXMgdG8gJiMzOTttYWtlIHNlbnNlJiMzOTsuIEZvciBleGFtcGxlLCBmb3IgYW55IHR3byBkaWZmZXJlbnQgZWxlbWVudHMgeCBhbmQgeSwgZXhhY3RseSBvbmUgb2YgbGVzcyh4LHkpIGFuZCBsZXNzKHkseCkgc2hvdWxkIGJlIHRydWUuIEZvciB0aGUgcHVycG9zZSBvZiB0aGlzIHByb2JsZW0sIGFuIGFycmF5IGlzIHNvcnRlZCB3aGVuIHRoZXJlIGFyZSBubyBpbnZlcnNpb25zIHdpdGggcmVzcGVjdCB0byB0aGUgY29tcGFyaXNvbiBmdW5jdGlvbi4gQW4gaW52ZXJzaW9uIHdpdGggcmVzcGVjdCB0byBsZXNzKHgseSkgaW4gYW4gYXJyYXkgQSBvZiBzaXplIG4gKGluZGV4ZWQgZnJvbSAwKSBpcyBhIHBhaXIgb2YgaW50ZWdlcnMgMCAmbGU7IGkgJmx0OyBqICZsdDsgbiBzdWNoIHRoYXQgbGVzcyhBW2pdLCBBW2ldKSA9IHRydWUgKG5vdGUgdGhhdCB0aGlzIG1heSBub3QgYmUgZXF1aXZhbGVudCB0byBsZXNzKEFbaV0sIEFbal0pID0gZmFsc2UpLjxcL3A+XHJcblxyXG48cD5VbmZvcnR1bmF0ZWx5LCBzb21lIHByb2dyYW1tZXJzIGFyZSBub3QgdmVyeSBjYXJlZnVsIGluIGRlXHVmYjAxbmluZyB0aGUgY29tcGFyaXNvbiBmdW5jdGlvbi4gSW4gc3VjaCBjYXNlcywgdGhlcmUgbWF5IGJlIG5vIHdheSB0byBzb3J0IHRoZSBlbGVtZW50cyBpbiBhbiBhcnJheSB0byBzYXRpc2Z5IHRoZSBjb21wYXJpc29uIGZ1bmN0aW9uLiBUaGUgYmVzdCB3ZSBjYW4gZG8gaXMgdG8gcHJvZHVjZSBhIHBlcm11dGF0aW9uIG1pbmltaXppbmcgdGhlIG51bWJlciBvZiBpbnZlcnNpb25zIHdpdGggcmVzcGVjdCB0byB0aGUgZ2l2ZW4gY29tcGFyaXNvbiBmdW5jdGlvbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZvciBlYWNoIGNhc2UsIGFuIGludGVnZXIgbiwgMSAmbGU7IG4gJmxlOyAxOCwgaW5kaWNhdGluZyB0aGUgc2l6ZSBvZiB0aGUgYXJyYXkgaXMgZ2l2ZW4gb24gb25lIGxpbmUuIFRoZSBlbGVtZW50cyBpbiB0aGUgYXJyYXkgYXJlIGxhYmVsbGVkIDAsIDEsIDIsIC4uLiwgbi0xLiBUaGUgbmV4dCBuIGxpbmVzIGVhY2ggY29udGFpbnMgYSBiaW5hcnkgc3RyaW5nIG9mIGxlbmd0aCBuLCB3aXRoIHRoZSBqIHRoIGNoYXJhY3RlciBvZiB0aGUgaSB0aCBsaW5lIGluZGljYXRpbmcgdGhlIHJlc3VsdCBvZiB0aGUgY29tcGFyaXNvbiBmdW5jdGlvbiBsZXNzKGksIGopICgwIG1lYW5zIGZhbHNlIGFuZCAxIG1lYW5zIHRydWUpLiBUaGUgZW5kIG9mIGlucHV0IGlzIGluZGljYXRlZCBieSBhIGNhc2UgaW4gd2hpY2ggbiA9IDAuIFRoZSBsYXN0IGNhc2Ugc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSwgb3V0cHV0IHRoZSBwZXJtdXRhdGlvbiB0aGF0IGhhcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGludmVyc2lvbnMgd2l0aCByZXNwZWN0IHRvIHRoZSBnaXZlbiBjb21wYXJpc29uIGZ1bmN0aW9uLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIGludmVyc2lvbnMgaW4gdGhlIHBlcm11dGF0aW9uLiBJZiB0aGVyZSBhcmUgbXVsdGlwbGUgcGVybXV0YXRpb25zIHdpdGggdGhlIHNhbWUgbnVtYmVyIG9mIGludmVyc2lvbnMsIG91dHB1dCB0aGUgb25lIHRoYXQgaXMgbGV4aWNvZ3JhcGhpY2FsbHkgc21hbGxlc3QuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=