시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 179 60 43 43.434%

문제

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

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

입력

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

출력

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

예제 입력

10
1110100010

예제 출력

31
1 8
2 7
3 4
5 6
9 10

힌트

출처

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

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