PROBLEM LINK:
Author: M.S.Vignesh
Tester: Sudarsan S,Murugappan S
Editorialist: M.S.Vignesh
DIFFICULTY: EASY
PREREQUISITES: Math
PROBLEM:
The Cricket World Cup is currently taking place and there is high expectations on the Indian team to win the trophy. The conditions suggest that big scores are needed to win games. In order to score big, the batsmen need to score runs at a good strike rate. Given that a batsman has so far scored R runs in B balls, determine the minimum number of balls that he needs to face in order to attain a strike rate of S or higher. Also, the batsman can face only 200 balls overall. So if it is not possible to reach the strike rate S or higher within that, print -1. Assume that the batsman has complete control over the balls he faces and can score from 0 to 6 runs as he wishes in each delivery. NOTE: Strike Rate refers to the number of runs the batsman is expected to score in 100 balls given the number of balls faced so far and the number of runs scored so far. Eg- If a batsman has scored 4 runs off 10 balls then his strike rate is 40 (He is expected to score 40 runs in 100 balls going at this rate).
#CONSTRAINTS
-
1 ≤ B ≤ 200
-
0 ≤ R ≤ 6∗B
-
0 ≤ S ≤ 600
SOLUTION:
Claim 1:
The Strike rate of a batsman remains same or increases if he hits a six off a ball. If the batsman already had a strike rate of 600 and he hits a six, the strike rate is still 600. If the strike rate is less than 600 and he hits a six then the overall strike rate increases as 6 runs is the maximum that a batsman can score off a ball.
If the batsman already has the strike rate required or higher , we print 0. We now say that the batsman will hit a six off each delivery he faces as it will only increase his strike rate. After each delivery i that the batsman has faced and hit for a six, we calculate the runs required after B + i balls to have a strike rate of S using the formula:
Runs needed=ceil((S*(B+i)*1.00)/100);
If the batsman has achieved those runs by hitting sixes off each of the i balls, then we print the minimum value of i that gives us the answer. If B + i exceeds 200, then we print -1.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.