TheLuckyGameDivOne | Topcoder Archive

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.

Definition

Class:: TheLuckyGameDivOne
Method:: find
Parameters:: long, long, long, long
Returns:: int
Method signature:: int find(long a, long b, long jLen, long bLen)
(be sure your method is public)

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.

Examples

```
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
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.