ACM-UCPC
시간 제한1초메모리 제한128 MB
순위 순서로 팀을 훑으며 학교별 상한과 순위 구간 조건에 따라 본선 60팀을 뽑고 모자란 자리는 건너뛴 팀을 순위대로 뽑습니다.
문제
2020년, 태양계 지구의 전산학 학회인 ACM(Association for Computing Machinery)이 대학생 프로그래밍 경시대회 ACM-UCPC(Universal Collegiate Programming Contest)를 연다. 시간과 장소의 제약 때문에 예선은 인터넷으로 치른다.
예선이 끝나면 각 팀의 성적이 푼 문제 수와 페널티로 주어진다. 문제를 더 많이 푼 팀이 순위에서 앞서고, 푼 문제 수가 같으면 페널티가 적은 팀이 앞선다. 어떤 두 팀도 순위가 같지 않다. 순위대로 정렬된 예선 결과를 받아 본선에 나갈 60팀을 뽑는 프로그램을 작성하시오.
성적이 우수한 팀을 뽑되 한 학교에서 너무 많은 팀이 뽑히지 않도록, 순위가 높은 팀부터 차례대로 아래 규칙을 적용해 선발 여부를 정한다. 지금 보고 있는 팀의 학교에서 이미 선발된 팀 수를 , 그 학교가 예선에 낸 팀 수를 이라 하자.
- 가 이상이면 선발하지 않는다. 즉 한 학교에서 최대 팀까지만 뽑는다. 2팀이 참가했으면 최대 1팀, 3팀이 참가했으면 최대 2팀이다.
- 지금 보고 있는 팀의 전체 순위가 1위부터 10위까지이면 일 때만 선발한다.
- 전체 순위가 11위부터 20위까지이면 일 때만 선발한다.
- 전체 순위가 21위부터 30위까지이면 일 때만 선발한다.
- 전체 순위가 31위 이하이면 일 때만 선발한다.
선발된 팀이 60팀이 되면 그 자리에서 멈춘다. 규칙을 끝까지 적용하고도 60팀을 채우지 못하면, 아직 선발되지 않은 팀 중에서 순위가 앞선 팀부터 차례대로 뽑아 60팀을 채운다. 이렇게 채울 때는 위 규칙을 적용하지 않는다. 참가 팀이 60팀보다 적으면 모든 팀을 선발한다.
입력
입력은 표준 입력으로 받는다. 첫 줄에 테스트 케이스의 개수 ()가 주어진다. 각 테스트 케이스의 첫 줄에는 참가 팀의 수 ()이 주어지고, 이어지는 개의 줄에 팀 이름 team, 학교 이름 school, 푼 문제 수 solved, 페널티 penalty가 공백 하나로 구분되어 주어진다 (, ). team과 school은 공백이 없는 길이 20 이하의 문자열이다. 각 테스트 케이스의 개 줄은 순위가 높은 팀부터 차례대로 주어진다.
출력
출력은 표준 출력으로 한다. 각 테스트 케이스마다 선발된 팀 중 전체 순위가 가장 낮은 팀의 이름을 한 줄에 하나씩 출력한다.