OlympicGames
TCO08 Round 4 · 2008-01-21 · by ivan_metelsky
Problem Statement
There are N teams taking part in The Programming Olympic Games. They are numbered by integers between 0 and N-1, inclusive. According to the rules, the Games consist of many competitions. The three top scoring teams within each competition are awarded gold, silver and bronze medals. Within a single competition, there can be no ties, and a single team can win at most one medal. After the Games are over, the following rules are used to rank the teams:
- If two teams each have a different number of gold medals, the team with more gold medals is ranked higher. Otherwise, the next rule is used.
- If two teams each have a different number of silver medals, the team with more silver medals is ranked higher. Otherwise, the next rule is used.
- If two teams each have a different number of bronze medals, the team with more bronze medals is ranked higher. Otherwise, the lower numbered team is ranked higher.
The Games are now in progress and left competitions are left before the Games are over. You are given a
Team 0 is very strong in the disciplines represented by all of the remaining competitions. Therefore, they will definitely win gold medals in all of them. Return the worst possible final ranking for team 0, where 1 is the highest ranking, 2 is the second highest, and so on.
Notes
- The total number of gold medals, silver medals and bronze medals in the input will not necessary be equal to each other. This is because some medals in past competitions may have been cancelled. However, in each of the remaining competitions, all three medals will be awarded with no cancellations.
Constraints
- medals will contain between 3 and 50 elements, inclusive.
- Each element of medals will be formatted "GOLD SILVER BRONZE" (quotes for clarity), where GOLD, SILVER and BRONZE are integers between 0 and 10,000, inclusive, with no extra leading zeros.
- left will be between 0 and 10,000, inclusive.
{"0 0 0",
"1 0 0",
"1 0 0"}
1
Returns: 3
Team 0 will win gold in the one remaining competition, and the other two teams will win silver and bronze. Each team ends up with one gold medal, but since team 0 has no other medals, it will end up in 3rd place.
{"0 0 0",
"1 0 0",
"1 0 0"}
2
Returns: 1
Team 0 will end up with two gold medals, which is more than either of the other teams, so the silver and bronze medal counts don't matter here.
{"1 2 3",
"100 0 0",
"7 0 0",
"7 0 0",
"7 0 0",
"7 0 0"}
6
Returns: 4
Team 0 is guaranteed to rank lower than team 1 (because of gold medals). If two of the remaining four teams each wins 3 silvers, team 0 will rank lower than them as well.
{"0 7 6",
"6 0 0",
"6 1 1"}
6
Returns: 1
Team 2 would need 6 silver and 6 bronze medals to rank higher than team 0. Since it's impossible to win more than one medal in a single competition, this cannot happen, so team 0 is guaranteed to rank the highest.
{"0 10000 10000",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0",
"10000 0 0"}
10000
Returns: 1
{"0 5 5",
"5 0 0",
"5 0 10"}
5
Returns: 2
Team 2 can rank higher than team 0 if it gets 5 silvers.
{"0 1 1",
"3 0 0",
"3 0 0",
"3 0 1",
"3 1 0",
"3 1 1",
"3 1 1"}
3
Returns: 5
The following would be the worst scenario for team 0: Team 3 wins 2 silver medals, team 4 wins 2 bronze medals, team 5 wins 1 silver, and team 6 wins 1 bronze. Team 0 would rank 5th.
Submissions are judged against all 133 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class OlympicGames with a public method int worstPlace(vector<string> medals, int left) · 133 test cases · 2 s / 256 MB per case