RingCountry | Topcoder Archive

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.
```
4
```
```
1000
```
```
47
```
```
1
```
```
10000000
```
```
1
```
```
Returns: 4
```

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.