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:
- TheLuckyGameDivTwo
- Method:
- find
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int find(int a, int b, int jLen, int bLen)
- (be sure your method is public)
Constraints
- a will be between 1 and 4747, inclusive.
- b will be between a and 4747, 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
99
100
1
1
Returns: 0
96
99
4
2
Returns: 0
14
19
5
5
Returns: 0
1915
4451
2380
25
Returns: 0
3224
4554
334
151
Returns: 0
1222
2767
1482
1302
Returns: 0
4125
4664
285
61
Returns: 0
1280
3575
569
246
Returns: 0
2915
3271
20
2
Returns: 0
2027
3742
1379
638
Returns: 0
911
1254
237
103
Returns: 0
160
2650
1563
1480
Returns: 8
3995
4179
145
95
Returns: 0
3373
4742
461
336
Returns: 4
2259
4617
1020
650
Returns: 0
2592
2867
182
73
Returns: 0
77
474
96
65
Returns: 0
44
774
165
58
Returns: 0
77
777
364
54
Returns: 0
44
477
233
134
Returns: 0
74
777
569
246
Returns: 0
1915
4451
2537
2537
Returns: 2
3224
4554
1331
1331
Returns: 4
1222
2767
1546
1546
Returns: 0
1915
4451
1
1
Returns: 1
3224
4554
1
1
Returns: 1
1222
2767
1
1
Returns: 0
157
4678
2261
1130
Returns: 0
694
4474
1890
945
Returns: 0
533
4627
2047
1023
Returns: 0
282
4479
2099
1049
Returns: 0
1
4747
2373
1186
Returns: 0
1
4747
1
1
Returns: 1
1
4747
4747
4747
Returns: 20
1
4747
8
3
Returns: 1
1
4747
4
2
Returns: 0
777
4444
3667
3666
Returns: 0
777
4444
3668
3668
Returns: 2
777
4444
3668
3667
Returns: 1
1
4747
1052
81
Returns: 0
1
4747
446
373
Returns: 6
1
4747
1899
345
Returns: 0
1
4747
19
4
Returns: 0
1
4747
2109
1
Returns: 0
1
4747
2825
99
Returns: 0
1
4747
1223
490
Returns: 4
1
4747
962
397
Returns: 4
1
4747
1412
898
Returns: 4
1
4747
696
351
Returns: 4
1
4747
379
198
Returns: 2
765
4376
6
5
Returns: 2
575
4206
86
27
Returns: 1
640
4086
8
3
Returns: 1
27
3516
3360
2646
Returns: 4
7
87
71
30
Returns: 1
48
854
752
359
Returns: 2
1
4747
2400
1998
Returns: 8
1
4747
3000
1500
Returns: 0
44
44
1
1
Returns: 1
1
4747
5
3
Returns: 1
1
4747
1000
500
Returns: 4
1237
4437
103
97
Returns: 0
1
4747
2000
1000
Returns: 0
3
5
3
3
Returns: 1
8
77
70
30
Returns: 0
1
4747
2373
1180
Returns: 0
1
4747
2350
1200
Returns: 0
1
4747
2372
1186
Returns: 0
444
444
1
1
Returns: 1
1
4747
4543
4513
Returns: 16
1
4747
2000
400
Returns: 0
73
75
2
2
Returns: 1
1
4747
2747
1274
Returns: 0
1
4000
350
79
Returns: 0
1
4747
3
2
Returns: 1
1
4747
600
300
Returns: 4
1
100
2
2
Returns: 1
1
4747
4600
2000
Returns: 0
8
4747
2000
800
Returns: 0
100
4747
100
98
Returns: 4
44
45
1
1
Returns: 1
1
4747
2300
1200
Returns: 0
4
4
1
1
Returns: 1
1
4747
50
3
Returns: 0
3
8
4
4
Returns: 2
1
6
3
2
Returns: 1