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.)
Definition
- Class:
- Catchphrase
- Method:
- reconstruct
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int reconstruct(int Ascore, int Bscore)
- (be sure your method is public)
Constraints
- Ascore will be between 0 and 10^6, inclusive.
- Bscore will be between 0 and 10^6, inclusive.
Examples
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.
1400
400
Returns: -1
400
1400
Returns: -1
0
1500
Returns: 0
500
1000
Returns: 1
1000
500
Returns: 1
1500
0
Returns: 2
2200
2600
Returns: 15
4400
200
Returns: 19
200
1900
Returns: 2
1100
1900
Returns: 10
1700
3000
Returns: 13
3600
900
Returns: 17
700
700
Returns: -1
2400
2200
Returns: 16
800
3100
Returns: 8
4700
900
Returns: 19
1700
2600
Returns: 13
393153
582719
Returns: -1
4900
2200
Returns: 21
700
3900
Returns: 7
1200
800
Returns: 3
646692
507855
Returns: -1
1800
600
Returns: 9
2600
3100
Returns: 17
2000
600
Returns: 10
1500
2400
Returns: 12
685300
896800
Returns: 1381
862300
440200
Returns: 1736
4100
3400
Returns: 19
947500
209000
Returns: 1907
0
300
Returns: -1
2300
3500
Returns: 16
864129
895412
Returns: -1
0
800
Returns: -1
2900
700
Returns: 15
1600
2600
Returns: 12
175536
819874
Returns: -1
2800
2300
Returns: 16
2300
3100
Returns: 15
1500
1600
Returns: 11
1000
2400
Returns: 9
1700
1900
Returns: 13
597634
631962
Returns: -1
3400
3100
Returns: 18
606352
863723
Returns: -1
1800
3500
Returns: 13
3900
2200
Returns: 19
1700
1500
Returns: 13
668500
562700
Returns: 1349
1900
1500
Returns: 14
2800
1500
Returns: 17
128597
543688
Returns: -1
2500
2300
Returns: 15
1700
1100
Returns: 11
1000
1600
Returns: 9
4900
700
Returns: 20
700
2400
Returns: 7
3600
2600
Returns: 19
1900
1100
Returns: 12
4800
2300
Returns: 20
4100
1400
Returns: 19
2400
3500
Returns: 16
161469
810712
Returns: -1
2300
1500
Returns: 16
1000
800
Returns: 1
1000
4400
Returns: 9
1700
3900
Returns: 13
395600
963000
Returns: 803
1900
300
Returns: 6
200
2400
Returns: 2
3900
1500
Returns: 19
3100
0
Returns: 14
1600
1100
Returns: 10
2000
1900
Returns: 14
2800
800
Returns: 14
3400
1100
Returns: 18
2900
1900
Returns: 16
3600
1400
Returns: 18
1900
3500
Returns: 14
134497
73929
Returns: -1
672543
950667
Returns: -1
2800
3500
Returns: 17
616800
58200
Returns: 1245
1800
1500
Returns: 13
1600
700
Returns: 7
3700
3000
Returns: 20
1900
3100
Returns: 14
2200
2800
Returns: 15
3800
1500
Returns: 19
1100
2100
Returns: 10
238900
378800
Returns: 489
1000
3700
Returns: 9
3600
1100
Returns: 19
2000
700
Returns: 10
1800
1200
Returns: 12
429622
790457
Returns: -1
3900
3500
Returns: 19
741435
443585
Returns: -1
654037
800070
Returns: -1
1500
2100
Returns: 12
2200
1600
Returns: 15
1700
2400
Returns: 13
500
3700
Returns: 5
700
100
Returns: -1
1300
1700
Returns: 11
1100
900
Returns: 2
1500
1700
Returns: 12
701100
798400
Returns: 1413
2400
1200
Returns: 15
3800
3500
Returns: 19
3700
1500
Returns: 20
2200
800
Returns: 11
1700
1600
Returns: 12
1000
2100
Returns: 9
1400
2900
Returns: 11
671466
865266
Returns: -1
2600
2100
Returns: 17
1000
1700
Returns: 9
2500
2400
Returns: 15
1400
2500
Returns: 11
2300
2000
Returns: 16
100
1300
Returns: -1
500
2100
Returns: 5
900
2900
Returns: 9
1200
2600
Returns: 10
1700
1300
Returns: 11
4300
1500
Returns: 20
3100
500
Returns: 16
1600
1600
Returns: 12
2100
2100
Returns: 15
3100
4100
Returns: 18
2000
2400
Returns: 14
889782
122980
Returns: -1
248200
467100
Returns: 507
700
1700
Returns: 7
2700
2900
Returns: 16
3700
800
Returns: 17
3200
2100
Returns: 17
5100
0
Returns: 21
1600
1200
Returns: 11
753700
430300
Returns: 1518
951800
38400
Returns: 1915
3900
1200
Returns: 19
1200
1800
Returns: 10
500
1800
Returns: 5
41546
618505
Returns: -1
1400
1800
Returns: 11
2900
2500
Returns: 17
2500
4400
Returns: 15
28700
224400
Returns: 68
3200
1300
Returns: 17
2700
2100
Returns: 16
1000
600
Returns: 1
413634
872614
Returns: -1
4800
800
Returns: 19
1400
1400
Returns: 10
3600
1600
Returns: 19
513420
767606
Returns: -1
1200
4600
Returns: 10
208500
478600
Returns: 428
1600
3600
Returns: 12
900
1800
Returns: 8
2100
4100
Returns: 15
2400
2500
Returns: 16
192394
13414
Returns: -1
1800
1300
Returns: 11
1500
2600
Returns: 12
3700
2800
Returns: 18
2200
2100
Returns: 15
3100
2100
Returns: 18
4900
2500
Returns: 21
900
1400
Returns: 5
1200
1100
Returns: 8
1100
1400
Returns: 7
979400
887900
Returns: 1969
2700
900
Returns: 14
1200
3800
Returns: 10
0
1000
Returns: -1
2400
1700
Returns: 16
3200
600
Returns: 16
800
2600
Returns: 8
802900
754600
Returns: 1617
736800
992100
Returns: 1484
1000
2600
Returns: 9
1700
2100
Returns: 13
2900
500
Returns: 15
1400
3400
Returns: 11
3200
3800
Returns: 17
3600
3600
Returns: 19
494600
503400
Returns: 1000
2100
3400
Returns: 15
1000
2200
Returns: 9
781652
511776
Returns: -1
1300
1900
Returns: 11
400
1000
Returns: -1
1500
1900
Returns: 12
2700
600
Returns: 13
1100
200
Returns: -1
1400
3500
Returns: 11
615500
882900
Returns: 1241
500
2600
Returns: 5
4400
1700
Returns: 20
2200
4600
Returns: 15
1700
1800
Returns: 12
4300
2000
Returns: 20
2500
2100
Returns: 16
500
2200
Returns: 5
2300
2600
Returns: 15
4900
500
Returns: 20
2500
2600
Returns: 16
5100
500
Returns: 21
1600
1700
Returns: 12
2900
3400
Returns: 16
100
1500
Returns: 1
4700
2900
Returns: 20
500
2300
Returns: 5
2400
200
Returns: 11
800
1100
Returns: 4
1100
3100
Returns: 10
3200
1800
Returns: 17
1200
1900
Returns: 10
1500
300
Returns: 2
2500
1800
Returns: 15
241700
123000
Returns: 496
1600
900
Returns: 7
2100
1400
Returns: 13
1400
1900
Returns: 11
991200
506600
Returns: 1993
1600
1400
Returns: 11
2900
2200
Returns: 17
800
300
Returns: -1
300
1100
Returns: -1
500
0
Returns: -1