Problem Statement
You have reached the final level of the game you are playing. This level consists of N+1 blocks, numbered from 0 to N from the left to the right. You start the level on block 0 and your goal is to reach block N exactly.
In this level, your character can make jumps of maximum length J. The character may jump both to the left and to the right, as long as they never leave the level.
A jump of length x will skip over x-1 consecutive blocks and land on the next (x-th) one in the direction of the jump. In particular, a jump of length 1 is simply a step to the next block on the left or on the right.
Block 0 is safe. All other blocks that form the level contain spiky traps that deal damage. More precisely, each time you land on block i, you receive T[i] damage.
Calculate and return the minimum total amount of damage you have to receive in order to reach block N.
In order to keep the input small, the damage is pseudorandom, as described below:
T[0] = 0
state = seed
for i = 1 to N:
state = (state * 1103515245 + 12345) modulo 2^31
T[i] = 1 + (state modulo M)
Definition
- Class:
- StepLeapSurviveTraps
- Method:
- minDamage
- Parameters:
- int, int, int, int
- Returns:
- long
- Method signature:
- long minDamage(int N, int J, int seed, int M)
- (be sure your method is public)
Notes
- The reference solution does not depend on the damages to be (pseudo)random, it would solve any input of the same size within the time limit.
Constraints
- N will be between 1 and 500,000, inclusive.
- J will be between 1 and 500,000, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
- M will be between 1 and 10^9, inclusive.
Examples
8
3
47
10
Returns: 17
The damage for the cells that form this level is as follows: T = {0, 9, 6, 9, 2, 9, 4, 1, 8}. Here, the optimal strategy is to only jump to the right, making jumps of lengths 2, 2, 3, and 1. This way, we'll receive a total of 6+2+1+8 = 17 damage.
100
1
47
123456789
Returns: 5835166389
With J = 1 the optimal strategy is to simply walk to the right and receive a total of sum(T) damage. For reference, the correct T looks as follows: T = {0, 78707731, 16700828, 54223987, 37397303, 112252759, 46678489, 43595839, 18674904, 13909121, 118477438, 88033399, 105356379, 57997612, 53876392, 95020013, 74587130, 65130672, 87137913, 21107663, 31915521, 93853982, 18919115, 39849879, 77942770, 35619505, 115508126, 38321619, 81217888, 48486089, 99385754, 3518042, 54541781, 56535927, 103271783, 118677266, 9471515, 42240439, 63756943, 22645319, 78498270, 24766051, 23259469, 97059690, 78644199, 106718369, 103400840, 52991972, 82679980, 11571002, 51967363, 92835245, 14642439, 8424125, 24743784, 97337616, 122077541, 1705829, 100021156, 109475123, 72076633, 108579776, 115648995, 69629823, 17743411, 112870250, 19785396, 23719093, 30779622, 32618435, 122368451, 78015617, 67622124, 44870230, 12344214, 55071073, 113446855, 52198724, 46857513, 99791617, 82202168, 19463620, 21983457, 19896614, 36547647, 10608455, 19619123, 19874030, 26282158, 63021190, 25389104, 82849251, 37721099, 93169629, 115038596, 6768175, 47951505, 65151308, 78430545, 36017979, 3777986}
5
5
12345
54321
Returns: 46038
Here the optimal solution is to cross the entire level in one jump, only receiving T[N] damage.
5
500000
12345
54321
Returns: 46038
446117
7
1948501517
442221
Returns: 5868464178
433741
116202
1685411311
567183
Returns: 263964
454857
1
2690834
502
Returns: 114419260
494877
133466
1355395163
486381
Returns: 19206
430152
219
1899324723
136
Returns: 3831
473524
3495
1468508435
182447
Returns: 36540
431276
2
1434210114
13
Returns: 1279149
475805
6167
417035555
1524540
Returns: 366030
491646
1471
2023059399
10236546
Returns: 7051845
454612
756
1123519141
2212
Returns: 3924
463431
916
1117738417
12095316
Returns: 20378599
479474
11
1631517495
49357
Returns: 317784755
479104
170184
1906477425
1
Returns: 3
471695
4
1141387247
127993
Returns: 4508579418
457096
2183
1138224035
521736534
Returns: 209624655
492823
1069
1043761029
108
Returns: 586
456575
43
2017745344
750198133
Returns: 334916779585
416761
10
1477705088
116963
Returns: 783099259
414166
483
1940892
1305216
Returns: 4744849
454272
6
88998632
277
Returns: 4940109
418407
63
863925910
66752839
Returns: 13354956554
469242
16711
317163642
41
Returns: 47
471230
1119
1007175254
4707981
Returns: 4417059
449640
8
380485713
567
Returns: 6067747
471808
756
649419618
202679
Returns: 459082
481131
304455
2109919775
1130
Returns: 674
415020
15034
1519313155
862013135
Returns: 394799710
473966
41920
272886230
80880
Returns: 64058
460458
16969
1866519440
37996468
Returns: 28377160
437700
40247
1052781061
3404
Returns: 825
421878
17124
421704849
4024309
Returns: 85493
460362
268
812974551
105636692
Returns: 1305041491
405359
503
1647993519
4
Returns: 813
468270
225958
1338728498
11548
Returns: 10883
495992
4
1309953612
6821
Returns: 253683940
470646
2493
400206914
248605238
Returns: 139093288
447255
3
242563618
957624612
Returns: 42298360143895
483091
386
904566712
726
Returns: 5667
460948
967
1891726748
1136
Returns: 1836
420352
1
1815666907
257000819
Returns: 52581972412106
468186
24829
1262555971
12
Returns: 28
416233
59
1445927722
60686
Returns: 14022665
430737
100021
1344280466
137118
Returns: 86067
479808
7879
770947798
3678464
Returns: 3679358
405609
43
334718070
59704
Returns: 24742040
407899
246
755530463
964105375
Returns: 9630569268
400585
7
3240676
8186
Returns: 97487159
497236
28613
526066028
118028
Returns: 41009
413383
7
1769321186
324411145
Returns: 3786170409981
480909
63
2043547395
19455
Returns: 4573271
451839
108448
1857911432
11687735
Returns: 438828
441469
4707
569139255
8284755
Returns: 882686
443654
12
2085040342
39776059
Returns: 201595270325
446813
1
349278773
759419
Returns: 169472206762
467606
96
1316725677
80443
Returns: 8021892
473682
3
761358727
48582
Returns: 2669880415
453001
1
1010397418
1833120
Returns: 415358337920
413987
1155
674631869
317660
Returns: 347803
431324
37
608660236
87575
Returns: 52461880
494212
36
398097787
28
Returns: 28795
500000
200000
17
128912
Returns: 120198
500000
500000
47
10
Returns: 6
500000
500000
1231245
1000000000
Returns: 726497646
500000
94679
18972347
3467289
Returns: 2610062
500000
500000
353245
1000000
Returns: 801342
500000
250000
547
214
Returns: 168
500000
500000
2147483647
999999999
Returns: 479385824
294047
3606
2102157703
88
Returns: 154
100000
100
10
10
Returns: 1086
500000
100000
1145141
5474747
Returns: 2844688