시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 131 | 45 | 29 | 65.909% |
축구 토너먼트에는 총 n개 팀이 참가한다. 첫 번째 라운드에서 총 n/2개의 경기가 열리게 된다. 매 라운드가 끝난 다음에, 승리한 팀은 다음 라운드에 진출한다. 두 번째 라운드에는 총 n/4개의 경기가 열리게 된다. 마지막에는 두 팀이 결승전에 올라오게 된다. 결승전의 승자는 토너먼트의 승자가 된다.
선영이는 한 축구 팀의 구단주이다. 이 팀은 세계에서 가장 축구를 잘하는 팀은 아니지만, 꽤 잘하는 팀이다. 선영이네 축구팀은 토너먼트에 참가한 팀중 적어도 절반은 쉽게 이길 수 있다. 또, 선영이네 팀이 이기지 못하는 모든 팀 t에 대해서, 그 팀을 이길 수 있으면서 선영이네 팀에게 지는 팀 t'가 항상 존재한다.
선영이네 팀이 토너먼트에 우승할 수 있게 토너먼트 스케줄을 작성하는 프로그램을 작성하시오.
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 토너먼트에 참가하는 팀의 수 n이 주어진다. (2 ≤ n ≤ 1024, n은 2의 제곱꼴) 팀은 1번부터 n번까지 번호가 매겨져 있으며, 선영이네 팀의 번호는 1이다.
다음 n개 줄에는 n자리 바이너리 스트링이 주어진다. j번째 줄의 k번째 숫자가 1인 경우에는 팀 j가 팀 k를 이길 수 있는 것이고, 다른 경우는 모두 0이다. (토너먼트 경기이기 때문에, 비기는 경우는 존재하지 않는다)
팀은 자기 자신과 경기를 할 수 없기 때문에, j번째 줄의 j번째 숫자는 항상 0이다. j와 k가 다른 경우에, j번째 줄의 k번째 숫자와 k번째 줄의 j번째 숫자는 다르다.
각 테스트 케이스에 대해서, 선영이네 팀이 승리할 수 있는 토너먼트 스케줄 n-1개 줄을 출력한다.
첫 n/2개 줄은 토너먼트의 첫 번째 라운드, 다음 n/4개 줄은 두 번째 라운드, ... 마지막 줄은 결승전이다.
각 줄은 두 정수 x와 y로 이루어져 있어야 한다. 이 뜻은 팀 x와 팀 y가 경기를 한다는 뜻이다.
만약, 팀1이 우승할 수 있는 스케줄이 여러 가지인 경우 아무거나 출력한다.
4 0110 0011 0000 1010 8 00111010 10101111 00010010 01000101 00110010 10101011 00010000 10101010
1 3 2 4 1 2 1 5 3 7 4 8 2 6 1 3 4 2 1 4
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2012 F번