dlaud5379   1년 전

(DeepL로 영어로 번역한 텍스트를 중역했습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

러시아 전국 학생 고생물학 팀 올림피아드의 예선이 곧 시작된다. 이번 대회에는 n개의 학교가 참여하며, 각 학교당 정확히 두 팀을 구성했다. 그런데 모든 팀이 자리를 잡은 뒤에 운영진이 같은 학교의 팀끼리 너무 가까이 앉아있는 것을 보고 참가자 자리 배치라는 어려운 문제를 직면하게 되었다.

대회장에는 일렬로 늘어선 2n개의 테이블에 각각 한 팀씩이 자리를 잡고 있으며, 인접한 테이블 사이의 간격은 10m이다. 운영진은 같은 학교의 두 팀 사이의 최소 거리가 가장 크게 되도록 자리 배치를 변경하고자 한다.

팀의 자리를 바꿀 때는 팀이 대회에 가져온 모든 물품을 같이 옮겨야 하기 때문에, 운영진은 위의 조건을 만족하면서 각 팀이 이동해야 하는 거리의 총합을 최소화하고자 한다.

예를 들어, 1번부터 4번까지의 학교가 대회에 참여하며, 1, 3, 2, 2, 1, 4, 4, 3의 순서대로 자리를 잡았다고 하자(각 팀을 출신 학교의 번호로 나타내었다). 이 자리 배치에서는 2번 학교와 4번 학교의 두 팀이 너무 가까이 붙어있게 된다. 운영진이 자리 배치를 1, 3, 2, 4, 1, 3, 2, 4로 바꾸면 각 학교의 두 팀이 40m 이상 떨어지게 되며, 이 거리가 최댓값이 된다. 또한 각 팀이 원래 자리에서 새로운 자리로 이동하는 거리의 합은 0 + 0 + 0 + 20 + 0 + 20 + 30 + 10 = 80m로, 이 거리 역시 주어진 자리 배치에 대해 최솟값이 된다.

2n개의 팀의 자리 배치 정보가 주어진다. 같은 학교의 두 팀 사이의 최소 거리가 최대가 되도록 자리 배치를 변경하는 프로그램을 작성하여라. 답이 여러 개인 경우, 각 팀이 이동하는 거리의 총합이 최소여야 한다.

입력

첫째 줄에 대회에 참여하는 학교의 수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄에 현재의 자리 배치 a1, a2, ..., a2n이 공백으로 구분되어 주어진다. 모든 i에 대해 ai는 i번째 팀의 출신 학교를 의미하며, 1 이상 n 이하의 정수가 정확히 두 번씩 들어옴이 보장된다.

출력

같은 학교의 두 팀 사이의 최소 거리가 최대가 되는 새로운 자리 배치를 공백으로 구분하여 한 줄로 출력한다. 정답이 여러 개일 경우 각 팀이 이동하는 거리의 총합이 최소가 되는 자리 배치를 출력한다. 그래도 정답이 여러 개일 경우 아무거나 출력한다.

댓글을 작성하려면 로그인해야 합니다.