시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB148159743243.947%

문제

2n개의 점이 x축의 좌표 1,2,...2n에 놓여 있다. 그 중 n개는 검은 점이고, n개는 하얀 점이다. 하나의 검은 점과 하나의 하얀 점을 연결하여 한 쌍을 만들면, 모두 n개의 쌍이 만들어진다. 한 쌍의 점을 연결할 때는, 왼쪽 점에서 출발하여 수직으로 올라가고, 거기서 수평으로 오른쪽으로 간 후, 다시 수직으로 내려가서 연결하면 하나의 길이 생긴다. 이렇게 생긴 n개의 길들은 서로 겹쳐서는 안되고, 서로 교차해서도 안 된다. 모든 길의 거리의 합을 가장 작게 하도록 n개의 길을 만드는 프로그램을 작성하시오. 단, 거리의 단위는 수직, 수평 모두 1이다.

그림 1 그림 2

그림 1의 경우 다른 방법으로 연결할 수도 있지만, 위 방법이 최소 연결 방법이고 거리의 합이 31이다. 그림 2의 경우도 다른 방법이 있지만, 위 방법이 최소 연결이며 거리의 합은 40이다.

입력

첫째 줄에는 점의 개수를 나타내는 정수 2n이 주어진다. 2n은 100이하의 정수이다. 그 다음 줄에는 n개의 0과 n개의 1로 이루어진 문자열이 주어진다. 0은 하얀 점이고, 1은 검은 점이다. 왼쪽부터 차례로 좌표 1,2,...2n에 해당한다.

출력

첫째 줄에는 길의 거리의 합을 출력한다. 다음 n개의 줄의 각 줄에는 연결되는 한 쌍의 점들의 좌표를 나타내는 두 정수를 출력한다. 두 정수 사이에는 빈칸이 하나 있다. 앞의 정수가 뒤 정수보다 작아야하고, n개의 줄은 앞 정수가 커지는 순서로 출력한다.

예제 입력 1

10
1110100010

예제 출력 1

31
1 8
2 7
3 4
5 6
9 10

예제 입력 2

12
111000111000

예제 출력 2

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

출처

Olympiad > 한국정보올림피아드 > KOI 1999 > 고등부 1번

  • 문제의 오타를 찾은 사람: skdudn321