ChangesInTheLead
TCO19 Japan Regional · 2019-08-01 · by misof
Problem Statement
In a hockey game the score is a pair of numbers: the number H of goals scored by the home team and the number A of goals scored by the away team.
At some intermediate point during the game, the leader is the team that scored more goals so far. If both teams scored the same number of goals, there is no leader at that point in time.
At some intermediate point during the game, the most recent leader is the team that was most recently a leader during this game. (If there currently is a leader, that team is also the most recent leader. There is no most recent leader before the first goal of the game is scored.)
A change in the lead occurs whenever a goal is scored and the most recent leader immediately before the goal exists and differs from the most recent leader immediately after the goal.
For example, consider a match in which the score changed as follows: 0:0, 1:0, 1:1, 2:1, 2:2, 2:3, 2:4, 3:4, 4:4, 5:4, 6:4. In this match there were two changes in the lead: the first one was when the score became 2:3, and the second one was when the score became 5:4.
You are given the final score of a match, i.e., the
Constraints
- H will be between 0 and 250, inclusive.
- A will be between 0 and 250, inclusive.
- C will be between 0 and 250, inclusive.
7 0 0 Returns: 1
The home team scored seven goals in a row. There were no changes in the lead.
0 6 250 Returns: 0
This is impossible. Given that the final score is 0:6, the away team must have scored six goals in a row and there could not be any changes in the lead. Thus, there are no matches in which the final score is 0:6 and the number of changes in the lead is 250.
3 1 1 Returns: 1
There is exactly one sequence of goals that matches these inputs: the away team took an early lead 0:1 and then the home team scored three goals in a row.
6 4 2 Returns: 35
One of the 35 possibilities is the one mentioned in the problem statement.
6 7 3 Returns: 208
0 0 0 Returns: 1
The game in which nobody scores a goal has zero changes in the lead.
Submissions are judged against all 156 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChangesInTheLead with a public method int count(int H, int A, int C) · 156 test cases · 2 s / 256 MB per case