ACM-UCPC
Time limit1sMemory limit128 MB
Pick 60 finalists by scanning ranked teams under per-school caps and rank-band limits, then fill leftovers in rank order.
- Level
Easy3 of 10
- Topics
- Simulation, Implementation
- Solved
- No attempts yet
Problem
In 2020 the ACM (Association for Computing Machinery), the computing society of Earth in the Solar System, holds ACM-UCPC (Universal Collegiate Programming Contest) for university students. Limits on time and venue push the preliminary round onto the internet.
After the preliminary round each team has a score made of the number of problems solved and a penalty. A team that solved more problems ranks ahead of a team that solved fewer, and among teams that solved the same number the smaller penalty ranks ahead. No two teams share a rank. Given the preliminary results sorted by rank, write a program that picks the 60 teams for the final round.
The organizers want strong teams while keeping any one school from taking too many slots, so they walk the teams from the best rank down and decide each one with the rules below. Let be the number of teams from the current team's school that are already selected, and let be the number of teams that school entered.
- If is at least , the team is not selected. At most teams come from one school. A school that entered 2 teams gets at most 1, and a school that entered 3 teams gets at most 2.
- If the current team ranks 1st to 10th overall, it is selected only when .
- If it ranks 11th to 20th overall, it is selected only when .
- If it ranks 21st to 30th overall, it is selected only when .
- If it ranks 31st or lower overall, it is selected only when .
The walk stops the moment 60 teams are selected. If the rules run out before 60 teams are filled, the remaining slots go to the teams that were passed over, taken in rank order, and the rules above do not apply to those slots. If fewer than 60 teams entered, every team is selected.
Input
Input is read from standard input. The first line holds the number of test cases (). The first line of each test case holds the number of entered teams (), and each of the next lines holds a team name team, a school name school, the number of problems solved solved, and a penalty penalty, separated by single spaces (, ). team and school are strings of length at most 20 that contain no spaces. Within a test case the lines come in order from the highest rank down.
Output
Output is written to standard output. For each test case print the name of the selected team with the lowest overall rank, one name per line.