Problem Statement
The time it takes to travel from city i to city (i+1) by road and by flight is given by the i-th elements of roadTime and flightTime, respectively. roadTime can be generated from the following pseudocode:
roadTime[0] = roadFirst mod roadMod;
for i = 1 to N-1
roadTime[i] = (roadTime[i-1]*roadProd + roadAdd) mod roadMod;
// note that (roadTime[i-1]*roadProd + roadAdd) may overflow a 32-bit integer
flightTime can be generated similarly by using flightFirst, flightProd, flightAdd, flightMod.However, taking a flight risks the life of the king during takeoffs due to the technological limitations in the kingdom. Hence the queen has asked him to ensure that the total number of takeoffs during his entire journey does not exceed K.
To minimize the number of takeoffs, the king may choose to take a direct flight from city i to city i+j instead of separate flights from city i to city i+1, then from i+1 to i+2, ... and from i+(j-1) to i+j. The time taken for this flight is the sum of the times taken for the flights from i to i+1, i+1 to i+2, ..., i+(j-1) to i+j.
Return the minimum amount of time in which the king can reach his queen.
Definition
- Class:
- RoadOrFlightHard
- Method:
- minTime
- Parameters:
- int, int, int, int, int, int, int, int, int, int
- Returns:
- long
- Method signature:
- long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K)
- (be sure your method is public)
Constraints
- N will be between 1 and 400000, inclusive.
- roadFirst, roadAdd, flightFirst and flightAdd will each be between 0 and 100000, inclusive.
- roadProd, roadMod, flightProd and flightMod will each be between 1 and 100000, inclusive.
- K will be between 0 and 40, inclusive.
- K will be less than or equal to N.
Examples
3
14
1
2
10
18
1
10
17
1
Returns: 14
The pseudocode gives roadTime = {4, 6, 8} and flightTime = {1, 11, 4}. The fastest way to reach the queen is to take the road from city 0 to 1 and 1 to 2, and a flight from city 2 to 3.
3
4
1
2
10
1
1
10
17
2
Returns: 11
roadTime and flightTime are the same as in previous example. But now the king is allowed 2 takeoffs.
3
4
1
2
10
1
1
6
9
1
Returns: 12
roadTime = {4, 6, 8} and flightTime = {1, 7, 4}. Even though roadTime[1] < flightTime[1], it is best to take a direct flight from city 0 to city 3 which takes a total time of 1 + 7 + 4 = 12 units.
331999
65645
48613
81333
82122
2374
18997
3468
97383
10
Returns: 13625973966
337552
12367
19281
79400
76410
29402
38052
12277
1125
27
Returns: 187902412
364022
49002
93182
68992
24256
6455
42349
78059
3457
37
Returns: 626837051
390818
80265
2443
79745
89425
70540
63081
80108
59743
8
Returns: 11640825815
357873
65562
69040
57517
3858
20770
43599
74218
59113
10
Returns: 703712348
328643
30767
84901
38251
59635
4101
2640
25554
58220
32
Returns: 9160042289
321892
27427
66024
32895
19155
47042
12219
70670
67585
36
Returns: 3049502560
373349
73159
66640
32302
47575
92630
25277
83505
64174
15
Returns: 8588704461
329201
71398
6856
97639
36863
57965
8913
75211
72497
13
Returns: 6033579281
350325
69347
57632
30099
49983
10902
56586
62050
9145
1
Returns: 1609926100
318381
8024
74916
69931
13054
37829
99428
37516
25126
12
Returns: 2041620745
398062
61262
99992
15705
33601
72788
71714
11494
58115
2
Returns: 6686431826
308127
62373
60342
19984
1603
52899
66120
74558
94739
22
Returns: 251102814
364462
71537
50629
29551
27328
22426
87194
88225
93943
6
Returns: 5029039829
330950
97224
51662
23879
58133
91169
55244
84828
27127
1
Returns: 4472738874
338532
51526
62699
15377
85659
4408
99381
98836
55302
2
Returns: 8809082715
398677
29112
13923
83860
63976
97890
10038
53397
51802
1
Returns: 10319492679
346690
48019
33783
52606
29250
89651
76426
60666
77307
35
Returns: 5083447107
379869
61654
78060
1081
96040
20341
76233
36187
66868
10
Returns: 12764788286
367284
48012
55457
52887
6977
3710
59259
50747
40233
39
Returns: 1280806235
396552
6595
59528
14562
72340
70176
19806
76134
88012
10
Returns: 14491776705
332941
70773
63651
99059
73018
62262
52776
19565
17699
14
Returns: 2917097198
314845
5070
97901
17355
16290
77690
29339
70949
91833
11
Returns: 2421319791
305050
23235
24436
34622
30035
59687
14606
94186
76680
11
Returns: 4570861408
302309
12077
51069
81965
59941
79963
36152
37062
93545
11
Returns: 9009283522
398197
78385
8443
19217
15400
63235
39975
47979
63160
32
Returns: 3115398259
314632
3431
90757
22214
11624
56717
76844
1979
10364
20
Returns: 1628649882
336215
64371
43950
13067
79454
4948
7012
84995
69351
16
Returns: 11640057803
310164
58609
21621
28807
88277
33928
56657
65421
43531
8
Returns: 6563790034
306059
98448
26948
82606
34933
28532
68531
76215
13356
22
Returns: 2058567712
355227
17332
11299
11255
43702
66055
2038
56702
17482
7
Returns: 3104739382
306875
52885
9084
60085
82265
64752
97501
49625
62870
3
Returns: 9661283407
365048
57981
80953
34021
65846
57445
71808
22198
73895
36
Returns: 12109050334
396042
10229
82673
36050
43797
17888
67908
43621
19644
13
Returns: 3933455386
317102
75152
48822
81068
36452
80949
57556
62928
57838
35
Returns: 5786095244
343997
91758
80747
71460
54597
68741
85914
76851
22543
0
Returns: 9416678862
356140
33234
78176
99071
27414
95128
55732
11422
50282
20
Returns: 4892485088
340373
73710
83726
64598
65574
45406
31174
46971
60558
28
Returns: 10278911316
375825
99526
12726
26901
7206
49262
90622
94167
31433
19
Returns: 1353694655
375614
33810
75472
40243
55916
85842
88546
83176
18454
18
Returns: 3464371124
346279
48607
2267
99599
42812
8566
94156
34337
41788
18
Returns: 7344422942
349373
68003
71076
4870
26479
22019
78832
7988
81972
40
Returns: 4623064763
305551
5833
11384
89349
16167
46503
48256
17147
24090
40
Returns: 2521550764
388169
46773
9612
73872
8802
69949
93951
8483
76632
10
Returns: 1362378757
315161
71316
68897
16143
85448
13183
90920
49218
70528
5
Returns: 11485683933
400000
16349
65645
58903
81333
62905
2374
21305
3468
34
Returns: 694670064
400000
38583
34208
28512
37494
73460
57932
35075
50497
22
Returns: 7418474756
400000
83149
23025
64022
56274
93182
65726
24256
12917
9
Returns: 2564243108
400000
65640
86762
49762
90818
80265
2443
79745
89425
7
Returns: 17557659310
400000
63081
74931
59743
14922
45066
65562
78427
57517
5
Returns: 2912347360
400000
20770
43599
74218
59113
55607
19683
51867
93543
2
Returns: 11864675463
400000
58994
4101
7214
25554
55442
62541
21892
35806
32
Returns: 5105489764
400000
12995
16870
58759
24864
59148
60275
58119
73349
38
Returns: 5385839750
400000
66640
17116
47575
4965
25277
70912
64174
97062
8
Returns: 975486480
400000
71398
6856
97639
36863
57965
8913
75211
72497
13
Returns: 7331880480
400000
31606
69347
74035
30099
35017
10902
58660
62050
21
Returns: 6032784434
400000
74307
12011
27708
91871
59714
99047
55778
15290
21
Returns: 3069351625
400000
22065
172
98062
68376
99992
2178
33601
92796
29
Returns: 14662371354
400000
8202
53835
9247
8127
62373
60342
19984
1603
23
Returns: 325980991
400000
66120
61188
94739
69014
59606
71537
56126
29551
36
Returns: 5849713190
400000
22426
87194
88225
93943
52122
30936
18500
72740
6
Returns: 14543705205
400000
44093
91169
71336
84828
26751
75507
38532
65688
24
Returns: 13044341468
400000
13707
75152
25761
327
85981
38018
81775
98677
31
Returns: 65046580
400000
13923
64903
63976
2882
10038
33312
51802
42221
4
Returns: 847422180
400000
48019
33783
52606
29250
89651
76426
60666
77307
35
Returns: 5865377595
400000
54990
81732
40553
28917
26348
14501
78267
75877
4
Returns: 6825464432
400000
68515
44669
30899
53466
47921
17724
28476
26790
17
Returns: 5455638363
400000
71402
36290
32197
56015
56543
80967
11628
28272
18
Returns: 6428446196
400000
68182
55734
8037
23930
91788
23407
32300
4189
30
Returns: 852141206
400000
23121
55530
46373
43080
3202
27716
22631
70905
34
Returns: 8595267360
400000
57264
57839
3587
38560
16708
20046
81833
30847
3
Returns: 6156554389
400000
50666
54602
45786
45494
44123
10610
27844
35453
12
Returns: 7076229901
400000
93014
46988
90849
57716
11241
69687
42987
15571
35
Returns: 3092743771
5
85739
94847
93893
98392
92840
93802
93830
92790
3
Returns: 122365
400000
16349
65645
58903
81333
62905
2374
21305
3468
40
Returns: 694650306
400000
79069
38583
37552
28512
19281
73460
76410
35075
40
Returns: 5367211176
400000
38052
7556
1125
43507
56925
49002
5947
68992
40
Returns: 8718930549
1
16349
65645
58903
81333
62905
2374
21305
3468
1
Returns: 481
5
16349
65645
58903
81333
62905
2374
21305
3468
5
Returns: 7201
35
16349
65645
58903
81333
62905
2374
21305
3468
35
Returns: 60007
30
16349
65645
58903
81333
62905
2374
21305
3468
0
Returns: 1225005
1
16349
65645
58903
81333
62905
2374
21305
3468
0
Returns: 16349
811
45472
75714
82623
73728
32816
61304
713
8786
11
Returns: 3464172
728
73745
59774
79684
93855
93723
45307
89132
21877
1
Returns: 8073484
48021
57087
69715
27308
42312
32500
21529
13224
9569
20
Returns: 230055716
8224
75016
54884
97555
6443
19926
9376
96099
58119
2
Returns: 26692511
76
11925
93576
34198
38779
37771
29430
22731
55321
0
Returns: 1575081
109829
38351
40846
11533
86751
76536
45613
46849
97675
0
Returns: 4763247593
7917
18997
89392
69053
32481
98831
96252
54403
35552
40
Returns: 124651839
385777
586
10939
87843
31377
5913
53662
19265
6941
20
Returns: 1345874525
2
36706
11826
77486
60981
422
22731
43758
12282
2
Returns: 7574
6320
47905
14292
93770
99155
90378
15041
25823
3206
33
Returns: 10327700
6320
47905
14292
93770
99155
90378
15041
25823
3206
33
Returns: 10327700
6397
44065
56226
4388
68905
36378
76486
87158
13559
0
Returns: 219769458
78469
50583
78190
73091
85787
75218
98256
63204
50812
33
Returns: 2003243669
106
39119
98795
94804
83110
46251
45898
85880
99157
27
Returns: 3154663
9304
49049
53263
41777
66236
14669
94912
75678
45182
15
Returns: 212441613
400000
85739
94847
93893
98392
92840
93802
93830
92790
40
Returns: 18454523790
400000
85739
94847
93893
98392
92840
93802
93830
92790
3
Returns: 18492207799
400000
1
2
3
4
5
6
7
8
9
Returns: 400000
40000
85739
94847
93893
98392
92840
93802
93830
92790
40
Returns: 1816282005
40000
14
1
2
10
18
1
10
17
40
Returns: 159680
400000
99993
99993
99993
99993
99993
99993
99993
99993
40
Returns: 0
400000
32543
2344
5436
53543
45
5354
345
34456
40
Returns: 6922906917
400000
121
4563
10101
100000
14104
11
101
92111
40
Returns: 18388529623
399987
42
1337
666
99991
77
78
103
99989
37
Returns: 19781004079
400000
100000
94568
92356
91123
91245
93456
94533
92441
40
Returns: 18127087363
400000
32525
24526
34442
23472
13421
23424
37429
17865
40
Returns: 3570535001
400000
1
2
3
4
1
2
3
4
40
Returns: 400000
395483
24123
23423
23423
6234
3463
34563
23423
23235
39
Returns: 1277967190
400000
1
2
3
4
5
6
7
8
40
Returns: 400000
400000
99996
99995
99994
99993
99992
99991
99989
99987
40
Returns: 19564987098
400000
85739
94847
93893
98392
92840
93802
93830
1000
40
Returns: 187967571
400000
1
7
8
12345
1
54
123
12345
40
Returns: 2486226079
400000
56000
36000
36000
30000
36000
36000
30000
30000
39
Returns: 6000
399999
99999
99998
99997
99996
99995
99994
99993
99992
39
Returns: 15990770137
400000
0
100000
99999
100000
0
100000
99999
100000
38
Returns: 39999500001
400000
99793
99791
99787
99991
99593
99591
99597
99991
40
Returns: 19850324161
400000
234
512
43
123
423
423
123
42
40
Returns: 6198441
50
85739
94847
93893
98392
92840
93802
93830
92790
40
Returns: 1404811
400000
99999
1
0
100000
99999
1
0
100000
0
Returns: 39999600000
3
14
1
2
10
18
1
10
17
0
Returns: 18
400000
23
239
51
100000
123
1239
151
100000
39
Returns: 19896657800
400000
14
1
2
10
18
1
10
17
40
Returns: 1599680
400000
99999
1
0
100000
0
1
0
100000
0
Returns: 39999600000
400000
85739
94847
93893
98392
92840
93802
93830
92790
0
Returns: 19648498424
400000
14
1
2
10
18
1
10
17
0
Returns: 1600000
399998
99996
99995
99994
99993
99992
99991
99989
99987
40
Returns: 19564790180
40
28096
91234
58614
11231
92747
51369
33881
12051
40
Returns: 177049
3
11
10
28
59
1
1
20
100
2
Returns: 62