Problem Statement
Ring Country has a capital city and N towns. The towns are built on a circle around the capital and they are numbered from 0 to N-1 in clockwise order.
All roads in Ring Country are one-directional. There are three types of roads:
- Road from the capital city to town i with length Lout[i].
- Road from town i to town (i+1) modulo N with length Laround[i].
- Road from town i back to the capital city with length Lin[i].
The royal tax collector lives in the capital. She needs to visit all the towns to collect taxes. On each day she must start her trip in the capital, visit one or more towns and then return to the capital and terminate her trip there. The maximum total length traveled on each day is Lday.
Calculate and return the minimum number of days the tax collector needs to visit each of the towns at least once. (She may visit the same town on multiple days if she wants.) If she cannot visit all the towns, return -1 instead.
In order to keep the input size small, the road lenghts are pseudorandom. Please use the following pseudocode to generate your input.
state = seed
for i = 0 .. N-1:
state = (state * 1103515245 + 12345) modulo 2^31
Lout[i] = 1 + (state modulo Mout)
state = (state * 1103515245 + 12345) modulo 2^31
Laround[i] = 1 + (state modulo Maround)
state = (state * 1103515245 + 12345) modulo 2^31
Lin[i] = 1 + (state modulo Min)
Definition
- Class:
- RingCountry
- Method:
- travel
- Parameters:
- int, int, int, int, int, int
- Returns:
- int
- Method signature:
- int travel(int N, int Lday, int seed, int Mout, int Maround, int Min)
- (be sure your method is public)
Notes
- The reference solution does not depend on the input being random, it would correctly solve any input that matches the size constraints.
Constraints
- N will be between 2 and 100,000, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
- Lday, Mout, Maround and Min will each be between 1 and 10^9, inclusive.
Examples
4
100
123456789
60
40
50
Returns: 1
There are N = 4 towns around the capital city. The generated road lengths are as follows: Lout = { 31, 58, 29, 12 } Laround = { 12, 15, 14, 33 } Lin = { 31, 28, 49, 22 } During the generation of those arrays, the variable "state" has the following values: 231794730, 1126946331, 1757975480, 850994577, 1634557174, 707246327, 1397699428, 1035569613, 1904890498, 1335160211, 1434329552, 1273099721 The tax collector can visit all the towns in one day. The optimal route is capital-0-1-2-3-capital, its total length is 31 + 12 + 15 + 14 + 22 = 94.
4
71
123456789
60
40
50
Returns: 2
The same country as in Example 0 but now the maximum length traveled each day is only 71. There is no way to visit all the towns in one day. One possible solution for two days is to go capital-0-1-capital in one day (total length 71) and capital-2-3-capital in the other day (total length 65).
4
70
123456789
60
40
50
Returns: -1
The tax collector cannot reach town 1.
100000
1000000
47474747
2000
2000
2000
Returns: 101
This is a country of maximum size. The average road length in this country is approximately 1000. With Lday = 10^6 we can expect that the tax collector can visit slightly fewer than 1000 towns each day, so she should need a bit more than 100 days to collect all taxes.
2
1000000
47
1000
10
1000
Returns: 1
3
759
57
1000
1
1000
Returns: 1
Answer is 1 but only if you travel more than one complete cycle: C-0-1-2-0-1-C.
2
255999072
268543586
128654
1945526
24174
Returns: 1
3
398384431
1542245923
6
6
6
Returns: 1
4
5
1468508435
2507971
2507971
2507971
Returns: -1
5
27356
1647457924
15909
114494300
387439
Returns: -1
6
4530769
1123519141
94494
14415
276590639
Returns: -1
7
24
355519765
232351988
7815141
2771
Returns: -1
8
306
853308887
432
432
432
Returns: -1
9
268678067
1146177193
234
8736258
71002
Returns: 1
10
8148
778158833
21
133
51
Returns: 1
11
42677
1321413367
114587400
114587400
114587400
Returns: -1
99245
3
2101334812
519151
55849
2797255
Returns: -1
97578
6
97040700
19
19
19
Returns: -1
98800
9690
1554617535
103
103
103
Returns: 535
95451
75
1546714289
9231579
9231579
9231579
Returns: -1
99549
51533808
242563618
93141
93141
93141
Returns: 90
93427
991161
1997165977
438866246
1003
1
Returns: -1
96926
102
1964529467
171
171
171
Returns: -1
95515
197167964
2136870386
18213218
75198252
31513
Returns: 16712
92882
1
1708937855
28
33531870
937591722
Returns: -1
92006
75
1720060055
122400151
55525680
187003764
Returns: -1
95183
20
1705603794
96
96
96
Returns: -1
91518
3
1533974457
4047
65368319
1
Returns: -1
99978
2366812
1010397418
1240
2375
684
Returns: 51
92710
40
331716879
106686299
4950119
1262307
Returns: -1
90586
1948185
866820893
132964135
6770
14
Returns: -1
91656
3930714
1885893272
13
130030650
22891
Returns: 88880
90432
1346387
2119888712
1616
12
4
Returns: 1
94197
5857
1480332796
14607666
7761
81979605
Returns: -1
96924
8369982
1796636626
71486
71486
71486
Returns: 416
93763
37478609
1162101126
3
116344894
304824124
Returns: -1
91072
147942
2032222347
1443
261091346
6526
Returns: 91025
90097
13638
490428354
36127049
36127049
36127049
Returns: -1
95332
1
1480581755
3
4
32347735
Returns: -1
93128
234731
385572705
25
25
25
Returns: 6
90852
973634708
1897296966
2474352
2474352
2474352
Returns: 116
96888
112
1604168383
22696922
22696922
22696922
Returns: -1
90488
1
130904518
245957608
245957608
245957608
Returns: -1
99475
896
547953963
84877
5
2
Returns: -1
92009
1322
546676137
20227
516071
366941394
Returns: -1
90209
113210308
1838018123
13453473
13453473
13453473
Returns: 5776
96463
6
1616927188
990
990
990
Returns: -1
91660
2715780
462328888
1
1
1
Returns: 1
92621
131657817
170833432
1357943
1357943
1357943
Returns: 480
94196
82079131
1420626755
11085
390959
902939807
Returns: 274
92557
165
1550258938
2979
2979
2979
Returns: -1
98877
35441
884531409
14770356
7394
15
Returns: -1
95354
78018
320615195
362
362
362
Returns: 223
99785
193
1672863266
29267708
393708
443027738
Returns: -1
91871
155889
628167979
371196
187972
8129
Returns: -1
98113
17558413
332609510
107508077
92582126
45
Returns: -1
93661
854970
383441804
10380821
2001952
10116
Returns: -1
91419
921689
1463139209
73317
125465
429136
Returns: 7452
97150
6056
1068579840
4
4
4
Returns: 41
99978
6908
1265713409
2691
2691
2691
Returns: 25901
91237
64707523
151130011
426422112
3281090
15195
Returns: -1
91236
850331850
1097067930
1519
12251217
562319
Returns: 654
93548
3
2034373739
1
1
1
Returns: 46774
99058
9
1785838395
462
462
462
Returns: -1
93066
7
1064632107
321970123
1512
214566
Returns: -1
93172
109708
2117736493
17455
62121
52
Returns: 23755
98972
1245881
927974519
86124
86124
86124
Returns: 3569
95912
1185
599247253
2276
284148
1437536
Returns: -1
91416
156928
1931177944
729134
729134
729134
Returns: -1
92359
48527
585226110
565100342
565100342
565100342
Returns: -1
93088
181000599
109238195
258713
275336034
12538631
Returns: 48469
96577
2781
769082629
1892871
1892871
1892871
Returns: -1
94384
765540
398727950
7
7
7
Returns: 1
93865
729208681
1270390786
3288
3288
3288
Returns: 1
94737
564066
1251702483
28
28
28
Returns: 3
92398
24299896
1625351247
366361296
366361296
366361296
Returns: -1
96563
2619936
1375771134
31387114
59
48213
Returns: 2
90057
3760703
1103924062
74405
44211
63
Returns: 532
94274
12
1205196993
103
52423715
1369931
Returns: -1
94558
100
2070518832
85328
85328
85328
Returns: -1
93593
2401
952639852
338556
338556
338556
Returns: -1
94836
92
135606474
9933
792032
1
Returns: -1
95904
75
1803768730
3187921
5
3
Returns: -1
93728
24401
1575351904
7574
775744651
7
Returns: 93726
97637
139098432
995710929
151918461
151918461
151918461
Returns: -1
93168
4112
1678662569
65027
918057
16240
Returns: -1
2
255999072
268543586
128654
1945526
24174
Returns: 1
3
398384431
1542245923
6
6
6
Returns: 1
4
2507971
1468508435
27356
387439
94494
Returns: 1
5
14415
489349967
1193
6
2771
Returns: 1
6
306
853308887
1
1
1
Returns: 1
7
4059
1585910533
21
133
51
Returns: 1
8
42677
1321413367
3
6
19
Returns: 1
9
9690
2050067571
103
103
103
Returns: 1
10
75
1546714289
1
1
1
Returns: 1
11
102
1880671616
1
20
5
Returns: 1
99160
2478386
581846500
2
2
2
Returns: 1
90803
120
1840506704
13
3
17
Returns: 1655
99906
110712
1282909328
5857
5857
5857
Returns: 2737
96073
7761
573850115
3
31
1443
Returns: 202
93726
265257
1812898707
131
131
131
Returns: 24
98739
13638
914822941
3
4
25
Returns: 19
99853
15
1336545990
2
2
1
Returns: 11095
97984
113210308
2102970538
13453473
13453473
13453473
Returns: 6297
96463
990
1616927188
68
68
68
Returns: 3514
95573
5536424
633475780
1357943
1357943
1357943
Returns: 13849
94196
82079131
1420626755
11085
390959
881
Returns: 225
91827
2979
629135074
81
193
165
Returns: 3041
99699
110499
786294352
6
8129
29951
Returns: 3958
93109
11853
370040610
52
52
52
Returns: 209
93471
53
504504633
4
4
4
Returns: 4674
99978
6908
1265713409
7
7
7
Returns: 59
97373
3281090
1263893249
15195
115678
346592
Returns: 1769
93965
12251217
783339864
562319
405716
40
Returns: 1568
96592
3063
1903699727
7
7
7
Returns: 127
98719
1512
428277337
381
381
381
Returns: 14803
4
1000
47
1
10000000
1
Returns: 4
100000
999999
10025
5454545
44
566
Returns: 3
4
115
315
83
40
50
Returns: 1