Problem Statement
Some teams have competed in a programming contest.
Each team has made one or more submissions.
Each submission received some positive score.
The total score of a team is the sum of the scores of all their submissions.
The scoreboard is computed by sorting the teams according to their total scores.
If multiple teams are tied, they are sorted lexicographically, with smaller names being higher in the scoreboard.
The team on the top of the scoreboard is winning.
(Only one team is winning at any moment, even if there are multiple teams tied for the winning total score.)
The scoreboard contains one line for each team. For each team, the line has the following format: "TeamName S1/T1 S2/T2 ... SN/TN". Here:
Different teams may have different numbers of submissions, worth a different number of points, and submitted at different times. The submissions are not necessarily ordered: neither by score, nor by submission time.
You are given a String[] scores: the scores of all teams, generated long after the contest was over. Each element of scores describes one team in the format shown above. The elements of scores are not necessarily ordered: neither by total score, nor by team name.
You would like to know who won the contest. However, this isn't necessarily the team that is currently winning. This is because it is possible that the scoreboard contains some submissions that happened after the end of the contest.
You know that the duration of the contest was an integer between 1 and 10^9, inclusive. Apart from that, you have no information about the exact duration. If the duration of the contest is D minutes, only the submissions that have Ti strictly smaller than D should be counted towards the correct total scores.
Given the content of scores, we say that a team could have won the contest if it was winning for some value of D from the above range. For each team, determine whether that team could have won the contest. Return a int[] with the same number of elements as scores. For each valid i, element i of the return value should be 1 if the team described by scores[i] could have won the contest, or 0 if it couldn't.
The scoreboard contains one line for each team. For each team, the line has the following format: "TeamName S1/T1 S2/T2 ... SN/TN". Here:
- TeamName is the name of the team
- N is the number of submissions they made
- the values S1 through SN are the scores of those submissions
- the values T1 through TN are times in minutes: submission Si was made after Ti minutes of the contest have elapsed
Different teams may have different numbers of submissions, worth a different number of points, and submitted at different times. The submissions are not necessarily ordered: neither by score, nor by submission time.
You are given a String[] scores: the scores of all teams, generated long after the contest was over. Each element of scores describes one team in the format shown above. The elements of scores are not necessarily ordered: neither by total score, nor by team name.
You would like to know who won the contest. However, this isn't necessarily the team that is currently winning. This is because it is possible that the scoreboard contains some submissions that happened after the end of the contest.
You know that the duration of the contest was an integer between 1 and 10^9, inclusive. Apart from that, you have no information about the exact duration. If the duration of the contest is D minutes, only the submissions that have Ti strictly smaller than D should be counted towards the correct total scores.
Given the content of scores, we say that a team could have won the contest if it was winning for some value of D from the above range. For each team, determine whether that team could have won the contest. Return a int[] with the same number of elements as scores. For each valid i, element i of the return value should be 1 if the team described by scores[i] could have won the contest, or 0 if it couldn't.
Definition
- Class:
- ContestScoreboard
- Method:
- findWinner
- Parameters:
- String[]
- Returns:
- int[]
- Method signature:
- int[] findWinner(String[] scores)
- (be sure your method is public)
Constraints
- scores will contain between 2 and 100 elements.
- Each element of scores will have between 7 and 100 characters.
- The name of each team will have between 3 and 8 characters.
- All characters in each team name will be uppercase English letters ('A'-'Z').
- Each team will have at least one submission.
- The score for each submission will be between 1 and 999, inclusive.
- The time of each submission will be between 1 and 10^9 - 1, inclusive.
- All team names will be different.
- Each element of scores will be formatted as shown in the statement, with a single space used as a separator.
Examples
{"TVG 1/1 1/2 1/3", "AJI 1/4 1/5 1/6"}Returns: {1, 1 }If the duration of the contest were D = 1, there would be no valid submissions. Hence, the total score of each team would be zero and team "AJI" would be the winner due to having a lexicographically smaller name. If the duration were D = 2, the only team with a valid submission (and therefore the winner) would be team "TVG". Thus, in this setting each team can be the winner.{"GLP 1/114 1/195 1/171 1/19 1/146 1/29","BKPF 1/57 1/187 1/277 1/21 1/223 1/35"}Returns: {1, 1 }{"AAA 248/2 495/5 993/7","BBB 244/6 493/7 990/10", "CCC 248/2 495/5 993/10"}Returns: {1, 0, 0 }{"UBA 10/2 30/4 25/3 999/1000", "UNC 1/3 3/20 40/50", "UNLP 2/2 3/3 4/4 100/100", "UNR 999/1000000 999/999999", "UNS 999/100000000"}Returns: {1, 0, 1, 1, 0 }
Back to all problems