TheLuckyGameDivOne
SRM 510 · 2010-11-01 · by Vasyl[alphacom]
Problem Statement
John and Brus believe that the digits 4 and 7 are lucky and all others are not. According to them, a lucky number is a number that contains only lucky digits in its decimal representation.
John and Brus play the following game. Initially, there is an interval of integers between a and b, inclusive. Then, John choose a subinterval of the initial interval that contains exactly jLen numbers. Finally, Brus chooses a subinterval of John's subinterval that contains exactly bLen numbers. The outcome of the game is the total number of lucky numbers in Brus's subinterval.
John follows the optimal strategy that maximizes the outcome. Brus follows the optimal strategy that minimizes the outcome. Return the outcome of the game.
Constraints
- a will be between 1 and 10^10, inclusive.
- b will be between a and 10^10, inclusive.
- jLen will be between 1 and b-a+1, inclusive.
- bLen will be between 1 and jLen, inclusive.
1 10 2 1 Returns: 0
John will choose a subinterval containing two consecutive numbers. Then Brus will choose a subinterval containing just one of these two numbers. Since no two lucky numbers are consecutive, Brus will always be able to choose a subinterval containing no lucky numbers, so the outcome is 0.
1 100 100 100 Returns: 6
Here, John and Brus have no choice. The outcome of the game is the number of lucky numbers between 1 and 100, inclusive.
4 8 3 2 Returns: 1
John can choose one of the intervals [4; 6], [5; 7] or [6; 8]. In the first two cases Brus can choose a subinterval that contains no lucky numbers. However, in the last case, Brus will have to choose a subinterval that contains the lucky number 7. Therefore it is optimal for John to choose [6; 8], and the outcome is 1.
1 100 75 50 Returns: 2
99 100 1 1 Returns: 0
Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheLuckyGameDivOne with a public method int find(long long a, long long b, long long jLen, long long bLen) · 109 test cases · 2 s / 256 MB per case