Catchphrase
SRM 819 · 2021-12-02 · by misof
Problem Statement
This problem is about (a simplified version of) scoring in the TV show Catchphrase. In the TV show there are two contestants who solve puzzles. We will call the contestants A and B.
There are three rounds.
- In round 1 there are between 1 and 9 puzzles, and each of those awards 100 points to the player who solves it. (Only the faster solver gets the points for each puzzle. Some puzzles may remain unsolved, in which case nobody gets the points for that puzzle.)
- In round 2 there are between 1 and 9 puzzles, and each of those awards 200 points.
- In round 3 there is an unlimited number of puzzles, and each of those awards 500 points. (Puzzles in rounds 2 and 3 may also remain unsolved.)
Additionally, there are two bonus puzzles: after round 1 there is a bonus puzzle that will award 500 points to exactly one of the two players, and after round 2 there is another such puzzle that awards 1000 points.
You are given the final scores at the end of the third round: player A has Ascore points while player B has Bscore points.
Determine whether these final scores are possible. If not, return -1. If they are possible, determine and return the maximum number of puzzles player A could have solved. (This includes both regular puzzles in all three rounds and some of the two bonus puzzles.)
Constraints
- Ascore will be between 0 and 10^6, inclusive.
- Bscore will be between 0 and 10^6, inclusive.
900 900 Returns: -1
In each game one of the players will get the bonus puzzle after round 2, and as that puzzle awards 1000 points, a final score of 900 points each is not possible.
47 1953 Returns: -1
The number of points awarded by each puzzle is a multiple of 100, so these scores are clearly impossible.
1800 0 Returns: 5
We can deduce that player A must have solved both bonus puzzles (worth a total of 1500 points). Then there are two possibilities: either she solved three 100-point puzzles in round 1, or she solved one 100-point and one 200-point puzzle. In the first case she has solved a total of 5 puzzles, in the second case only 4, so we return the bigger number.
1100 2000 Returns: 10
A could have solved all nine puzzles in round 1 + one puzzle in round 2, while B solved both bonus puzzles and one puzzle in round 3.
4300 1100 Returns: 19
An optimal scenario looks as follows: in round 1 A solved 7 puzzles and B solved 1 puzzle (worth 100 each) A solved the first bonus puzzle (worth 500) in round 2 A solved 8 puzzles (worth 200 each) B solved the second bonus puzzle (worth 1000) in round 3 A solved 3 puzzles (worth 500 each) A has solved a total of 7 + 1 + 8 + 3 = 19 puzzles. There is no other scenario in which the final scores are the same and A has solved more than 19 puzzles.
Submissions are judged against all 238 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Catchphrase with a public method int reconstruct(int Ascore, int Bscore) · 238 test cases · 2 s / 256 MB per case