편향된 순위표
면접 대비시간 제한1초메모리 제한1024 MB
N개 팀의 희망 순위가 주어질 때, 팀마다 1부터 N까지 서로 다른 순위를 배정해 희망 순위와의 차이 합이 최소가 되는 값을 구합니다.
문제
대회 결과는 보통 참가자의 점수로 정해진다. 그러나 IPSC 다음 해부터는 방식을 바꿀 계획이다. 등록할 때 각 팀은 순위표에서 원하는 등수를 양의 정수 하나로 입력한다. 우리는 이 선호를 모두 반영해서, 대회가 끝나면 가능한 한 많은 팀을 만족시키는 순위표를 발표한다.
그런데 모든 요청을 만족시킬 수 없다면 순위표는 어떻게 될까?
순위표가 하나 있다고 하자. 각 팀에 대해 선호하는 등수와 순위표상의 등수 사이의 거리를 구한다. 이 거리들의 합을 그 순위표의 나쁨도라고 한다.
팀 이름과 선호 등수가 주어지면, 나쁨도가 최소가 되는 순위표를 하나 찾아라.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다.
각 테스트 케이스는 다음과 같다. 첫 줄에는 팀의 수 N이 주어진다. 다음 N줄에는 팀 이름(영문자와 숫자로 이루어진 문자열)과 선호 등수(1 이상 N 이하의 정수)가 주어진다. 같은 팀 이름은 없다. 팀 이름은 최대 20자이다.
출력
각 테스트 케이스에 대해, 주어진 팀들에 대한 최적의 순위표의 나쁨도를 정수 하나로 한 줄에 출력한다.
제한
- 1 ≤ T ≤ 20
힌트
첫 번째 테스트 케이스에서 최소 나쁨도를 갖는 순위표 중 하나는 다음과 같다.
1. noobz
2. llamas
3. Winn3rz
4. 5thwheel
5. NotoricCoders
6. WhoKnows
7. StrangeCase
두 번째 테스트 케이스에서는 모든 순위표가 똑같이 좋다.