Informatica Online Judge

  검은점과 하얀점 연결 [0745 / 02E9]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 10   Total Tried : 109


The Champion of this Problem (C++) : gs18012 - 0ms / 732byte
My Best Submission (C++) : N/A

[]

Background

2n개의 점이 x축의 좌표 에 놓여 있다.1,2,3,...,2n에 놓여있다. 그 중 n개는 검은 점이고 나머지 n개는 하얀 점이다.

하나의 검은 점과 하나의 하얀 점을 연결하여 한 쌍을 만들면, 모두 n개의 쌍이 만들어진다. 한 쌍의 점을 연결할 때는, 왼쪽 점에서 출발하여 수직으로 올라가고, 거기서 수평으로 오른쪽으로 간 후, 다시 수직으로 내려가서 연결하면 하나의 길이 생긴다.

이렇게 생긴 n개의 길들은 서로 겹쳐서는 안되고, 서로 교차해서도 안 된다. 모든 길의 거리의 합을 가장 작게 하도록 n개의 길을 만드는 프로그램을 작성하시오.

단, 거리의 단위는 수직, 수평 모두 1이다.



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

Input

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

Output

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

IO Example

입력
10
1110100010

출력
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

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]