시간 제한
메모리 제한
시간 제한
1초
메모리 제한
128 MB
2n개의 점이 x축 위의 좌표 1, 2, ..., 2n에 놓여 있다. 이 중 n개는 검은 점이고 n개는 하얀 점이다.
검은 점 하나와 하얀 점 하나를 연결하여 모두 n개의 쌍을 만들어야 한다. 한 쌍을 연결할 때는 좌표가 더 작은 점에서 수직으로 위로 올라간 뒤, 수평으로 오른쪽으로 이동하고, 다시 수직으로 내려와 다른 점에 도착하는 ㄷ자 모양의 길을 만든다. 각 길의 높이는 양의 정수로 정할 수 있다.
만들어진 길들은 서로 겹치거나 교차하면 안 된다. 수직 방향과 수평 방향 모두 거리의 단위는 1이다. 조건을 만족하도록 모든 점을 짝지을 때, n개 길의 총 거리 합이 최소가 되게 하라.
첫째 줄에 점의 개수를 나타내는 정수 2n이 주어진다. 2n은 100 이하의 짝수이다.
둘째 줄에 길이가 2n인 문자열이 주어진다. 문자열은 n개의 0과 n개의 1로 이루어져 있으며, 왼쪽부터 좌표 1, 2, ..., 2n에 놓인 점을 나타낸다. 0은 하얀 점, 1은 검은 점이다.
첫째 줄에 가능한 최소 총 거리 합을 출력한다.
다음 n개의 줄에는 연결되는 한 쌍의 점 좌표 a b를 출력한다. 항상 a < b여야 하며, 여러 줄은 a가 증가하는 순서로 출력한다.