Problem Statement
There is a wide river. Somebody placed a sequence of N+1 stones into the river along a line that goes from one river bank to the other. People can now use these stones to jump across the river.
We will number the stones from 0 to N. Stone 0 is on one bank of the river, stone N is on the other bank, the other stones lie between them in numerical order. For the purpose of this problem, assume that each stone is a point and that all these points lie on one straight line.
For each valid i, the distance between stones i and i+1 is equal to 1 + ((i*i) mod M). For example, if M = 10, the distance between stones 6 and 7 is 1 + (36 mod 10) = 1 + 6 = 7.
You want to get across the river by making at most J jumps, but you are afraid that your maximum jump length might be too short for that. Calculate and return the smallest L such that a person capable of making jumps of length at most L can get across the river in at most J jumps.
(When jumping across the river, the first jump must begin on stone 0; each jump must end on a stone; and in particular, the last jump must end on stone N.)
Definition
- Class:
- JumpAcrossTheRiver
- Method:
- minLength
- Parameters:
- int, int, int
- Returns:
- long
- Method signature:
- long minLength(int N, int M, int J)
- (be sure your method is public)
Notes
- It can be shown that the smallest L we seek is always an integer.
Constraints
- N will be between 1 and 1,000,000, inclusive.
- M will be between 1 and 10^9 + 7, inclusive.
- J will be between 1 and N, inclusive.
Examples
10
1
1
Returns: 10
There are 10+1 = 11 rocks in this river, and as M = 1, the distance between any two consecutive rocks is 1. Hence, the distance between the two banks of the river is 10. We want to get across this river in a single jump. Clearly, the jump length we need for that is at least 10.
10
1
3
Returns: 4
L = 4 is sufficient to get across this river in three jumps. E.g., we can jump from stone 0 (the first bank) to stone 3, from there to stone 6, and from there to stone 10 (the other bank). L = 3 is not sufficient (in three jumps we can only get to stone 9), so L = 4 must be optimal.
10
1234567
10
Returns: 82
Here we are allowed to make 10 jumps, which means that we can simply jump from one stone to the next. The longest jump we'll need to make is the jump from stone 9 to stone 10. The length of this jump is 82. Above we have shown that L = 82 is long enough. Now all that remains is to realize that a person with maximum jump length L = 81 cannot get to the other bank of this river at all, so L = 82 must indeed be optimal.
10
1234567
4
Returns: 87
If our maximum jump length is 87, we can get across this river in four jumps: from stone 0 to stone 6 (jump length 1+2+5+10+17+26 = 61), from stone 6 to stone 8 (jump length 37+50 = 87), from stone 8 to stone 9 (jump length 65) and from stone 9 to stone 10 (jump length 82).
123456
1000000007
2
Returns: 27561114912135
Watch out for integer overflow, in particular when computing the distances between consecutive stones.
998987
1000000007
989000
Returns: 999999938
998987
1000000007
603212
Returns: 1092605551
29
128654
6
Returns: 1513
94494
33064496
85092
Returns: 33064373
1
24
1
Returns: 1
27
3
5
Returns: 10
993762
8148
133
Returns: 29787937
879358
12
42677
Returns: 90
6
19
1
Returns: 42
102
171
1
Returns: 8021
946850
16802533
58
Returns: 136913399360
129166
4443723
1
Returns: 285056739668
963923
2366812
1240
Returns: 920222209
848031
41
40
Returns: 445237
5
2478386
4
Returns: 17
7761
81979605
8
Returns: 19484789042
7514
9877000
21
Returns: 1456999625
859619
1
3
Returns: 286540
959638
8247
4
Returns: 979700507
4831
234731
15
Returns: 36291433
112
22696922
2
Returns: 231133
947103
19211
1
Returns: 9026764284
896
84877
17
Returns: 1956308
991625
160
1322
Returns: 46928
830745
803
6
Returns: 54136950
922517
40355407
1
Returns: 18560485731421
1105
784
165
Returns: 2517
948010
6
81
Returns: 37064
871747
29267708
393708
Returns: 44380511
155889
371196
6
Returns: 4800891508
851997
28
117
Returns: 83755
11853
854970
52
Returns: 94471810
10116
921689
24
Returns: 187248464
429136
201003968
35488
Returns: 1268194995
982162
2691
17
Returns: 75551936
311397
3281090
24
Returns: 21234830368
346592
44720
15952
Returns: 491933
893205
1
240070
Returns: 4
919040
593677405
35776
Returns: 7737980778
1512
214566
5
Returns: 28298380
980608
1501688
284148
Returns: 3089530
2402
416501745
102
Returns: 46997500
955364
181000599
258713
Returns: 391954558
917576
1
17808
Returns: 52
501469
2772
289292
Returns: 3056
899
24299896
59
Returns: 4340125
861781
1
17
Returns: 50693
845775
63
102315
Returns: 231
8977
19967
3673
Returns: 30660
257446
100
22220
Returns: 507
876039
92
9933
Returns: 3513
930913
26925107
53
Returns: 235854731757
7574
3946
1
Returns: 15001249
959819
14861509
85577
Returns: 88250403
856391
12
20751
Returns: 175
827812
25856114
108
Returns: 98847634555
1
362
1
Returns: 1
2552
594751008
776
Returns: 9644552
873530
10852593
308
Returns: 15367918885
857136
2
31
Returns: 41475
832165
3415
20928
Returns: 67375
901670
1882
23
Returns: 36909651
56144
180437
6
Returns: 843155714
846467
225550367
4293
Returns: 22146883083
24890
131557444
1
Returns: 1316253225127
26
12446
19
Returns: 626
64364
343494966
1204
Returns: 8234473016
62
495620524
1
Returns: 77593
933755
3122108
374329
Returns: 4940593
36
22
3
Returns: 133
899771
1
95
Returns: 9472
901368
125955
5
Returns: 11306892985
850798
7137318
8
Returns: 379076263693
3
86327405
2
Returns: 5
13151
3363
2
Returns: 10943111
13
289346930
3
Returns: 267
850759
3036908
3
Returns: 430316114173
933746
8048921
24
Returns: 156396596135
111841
7
1424
Returns: 237
12
392
11
Returns: 122
894743
7
18
Returns: 149126
1157
1160
5
Returns: 125001
947026
252231
87889
Returns: 1435577
706243
2
4772
Returns: 222
63486
158026653
4
Returns: 1148717286002
992507
223935554
258300
Returns: 506823580
5852
16062
1843
Returns: 30520
158
68052327
2
Returns: 659001
2013
137
735
Returns: 226
20
52820
1
Returns: 2490
48
2930
3
Returns: 12390
2
10112
1
Returns: 3
21
5817
8
Returns: 437
801067
139176966
117
Returns: 473568728261
916184
502397
73309
Returns: 3305295
950993
928654566
29
Returns: 15024707626494
45878
4078
18195
Returns: 6396
877372
4023
342883
Returns: 6324
8
449231193
1
Returns: 148
958249
951830
792
Returns: 575280660
886422
254962024
433
Returns: 259093373323
830847
3445
467695
Returns: 4130
1000000
1000000006
50
Returns: 9869997907375
1000000
1000000000
10000
Returns: 49680147347
1000000
2341
34
Returns: 34441507