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
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
9347723696
9571920780
195615841
154218370
Returns: 0
2333393417
9544562943
3790188035
1306872028
Returns: 0
3434727064
5306990644
661022424
577260426
Returns: 512
3852497597
5052077036
106564945
81282281
Returns: 256
5729529199
6695255706
159262941
79824511
Returns: 0
1606852396
2164763569
87630290
41930822
Returns: 0
8823596914
9681161364
170880455
25195410
Returns: 0
3241098837
8853343676
5078969173
4259523817
Returns: 1024
96
2048347782
1480258452
318337601
Returns: 0
17
7808832881
5496032947
5153288770
Returns: 1024
64
6882562792
3360592841
2808641059
Returns: 512
97
5195708848
702456945
58522006
Returns: 0
99
9413414523
9128363832
6954249838
Returns: 768
1
10000000000
65038986
31016009
Returns: 128
1
10000000000
1683104052
769794991
Returns: 256
1
10000000000
5454765462
3256888704
Returns: 512
1
10000000000
9558222065
5684483791
Returns: 512
1
10000000000
4297339257
1957709038
Returns: 0
1
10000000000
10000000000
10000000000
Returns: 2046
1
10000000000
1
1
Returns: 1
1
10000000000
5000000000
2500000000
Returns: 256
47777
4444447474
2222199849
1111099924
Returns: 0
47444
4747477774
2373715165
1186857582
Returns: 0
74777
7774774777
3887350000
1943675000
Returns: 256
77744
4444744477
2222333367
1111166683
Returns: 0
447778
444447473
221999848
110999924
Returns: 0
447445
747477773
373515164
186757582
Returns: 128
7
88
66
39
Returns: 2
53
96361194
342
1
Returns: 0
398763
221391366
4
4
Returns: 2
1206
3726511
7
5
Returns: 1
2
21
12
9
Returns: 1
8
24
1
1
Returns: 0
37
54
4
4
Returns: 2
9
43
5
5
Returns: 0
3
4
1
1
Returns: 1
1
10000000000
913900914
407734
Returns: 0
1
10000000000
619939513
333666832
Returns: 256
1
10000000000
94301452
31377248
Returns: 64
7437
10000000000
50000000
49900000
Returns: 320
1
10000000000
1337
1331
Returns: 13
1
10000000000
10000000
1000
Returns: 0
1
9999999999
827382
827377
Returns: 125
40
46
3
2
Returns: 1
1
10000000000
2000000000
1300000000
Returns: 512
1
10
8
3
Returns: 1
5
10
3
2
Returns: 1
4
44
6
3
Returns: 1
200000
999999
11
7
Returns: 1
4774444445
5000000000
68
41
Returns: 2
6782916802
9934429950
1879588595
1075074264
Returns: 256
1
9999999999
5555555555
2222222222
Returns: 0
45
55
3
2
Returns: 1
1
10000000000
9999999997
3
Returns: 0
4444444444
4444444447
4
4
Returns: 2
1
10000000000
1543143244
1530344384
Returns: 768
40
51
8
3
Returns: 1
430
490
34
3
Returns: 0
444
477
34
33
Returns: 3
40
60
3
2
Returns: 1
4
4
1
1
Returns: 1
1
5
5
3
Returns: 0