# Codingame: Roller Coaster

## The Goal

## Rules

- People queue up in front of the attraction
- They can either be alone or in a group. When groups are in the queue, they necessarily want to ride together, without being separated.
- People never overtake each other in the queue.
- When there isn’t enough space in the attraction for the next group in the queue, the ride starts (so it is not always full).
- As soon as the ride is finished, the groups that come out, go back into the queue in the same order.

The attraction contains a limited number `L` of places.

The attraction can only function `C` number of times per day.

The queue contains a number `N` of groups.

Each group contains a number `Pi` of people.

Each person spends 1 dirham per ride.

## Example

`L`=3,

`C`=3 and 4 groups (

`N`=4) of the following sizes [3,1,1,2]:

**Ride 1: **for the first roller coaster ride, only the first group can get on and takes all the places. At the end of the ride, this group returns to the back of the queue that now looks as follows [1,1,2,3].*Earnings of the ride : 3 dirhams.*

**Ride 2 : **on the second ride, the following two single-person groups can get on, leaving one place empty (the group of 2 people that follows cannot be separated) At the end of the ride, they return to the back of the queue: [2,3,1,1]*Earnings of the ride : 2 dirhams.*

**Ride 3: **for the last ride (C=3), only the group of 2 people can get on, leaving one place empty. *Earnings of the ride : 2 dirhams.*

**Total earnings: **3+2+2 = 7 dirhams

## Game Input

**Input**

Line 1: The integers `L`, `C` and `N` separated by a space.

`N` following lines: Each line contains an integer `Pi` representing the number of people in a group. The lines are ordered in the same way as the queue. (The first lines correspond to the first groups that can get on the ride).

**Output**

`C`roller coaster rides)

**Constraints**

`Pi`≤

`L`

1 ≤

`L`≤ 10^7

1 ≤

`C`≤ 10^7

1 ≤

`N`≤ 1000

1 ≤

`Pi`≤ 10^6

## Solution

I really liked to solve this problem. We can do much better than the trivial solution, which simply loops \(C\) times. Or better said, we must do better, since \(C\) can become quite large. What I first did, was playing the game for a while. With the example input of (3, 1, 1, 2) and a limit of 3, this means:

\[\begin{array}{l} \leftarrow (3) \leftarrow (1, 1, 2)\\ \leftarrow (1, 1) \leftarrow (2, 3)\\ \leftarrow (2) \leftarrow (3, 1, 1)\\ \end{array}\]

After that, we always have the same groups. Let's try another example (2, 3, 5, 4) with a limit of 5:

\[\begin{array}{l} \leftarrow (2, 3) \leftarrow (5, 4)\\ \leftarrow (5) \leftarrow (4, 2, 3)\\ \leftarrow (4) \leftarrow (2, 3, 5) \end{array}\]

Last example: (3, 9, 7, 6, 4) with limit 15:

\[\begin{array}{l} \leftarrow (3, 9) \leftarrow (7, 6, 4)\\ \leftarrow (7, 6) \leftarrow (4, 3, 9)\\ \leftarrow (4, 3) \leftarrow (9, 7, 6)\\ \leftarrow (9) \leftarrow (7, 6, 4, 3) \end{array}\]

It's clear that this pattern must start to cycle eventually. So, the first step to solve this problem is to find the groups that emerge and the cycle offset. For the first two examples, the offset was zero, in the last example it was 1. I use a quite simple string representation as a fingerprint for the cycle detection. If we know the value of every individual group, all we have to do is how often each group will go. All the groups which don't cycle must be added exactly once to the final result. The number of these groups will be \(o\).

All other groups will need to go exaclty \(\left\lfloor\frac{C-o}{|g| - o}\right\rfloor\) times. Okay, not exactly. We need to fill the rest, if the number doesn't fill a full cycle. But we simply add one to each group as we go. The complete algorithm can then look like this:

var inputs = readline().split(' '); var L = +inputs[0]; var C = +inputs[1]; var N = +inputs[2]; var P = []; for (var i = 0; i < N; i++) { P.push(+readline()); } function compute(P, L, C) { var g = []; // Group value Storage var q = [P.toString()]; // Sequence Storage var t = P.shift(); // Pop the first value off the beginning var o; // Cycle offset var res = 0; // Final result // Calculate offset and groups do { var s = 0; // Generate a group for (var i = 0; i <= P.length && s + t <= L; i++) { P.push(t); // Push current value to back s+= t; // Sum for group t = P.shift(); // Pop a new value from the front } o = q.indexOf(P.toString()); // Check for Cycle offset q.push(P.toString()); // Remember current sequence g.push(s); // Found a new group } while (o === -1); // Loop until we get a cycle // Sum up the first elements occuring just once for (var i = 0; i < o; i++) { res+= g[i]; } // Calculate the rest, which doesn't fit into a group var r = (C - o) % (g.length - o); // Run over the other groups for (; i < g.length; i++) { // Group value times the number of occurences plus the rest res+= g[i] * (Math.floor((C - o) / (g.length - o)) + (r > 0)); r--; // Reduce rest } return res; } print(compute(P, L, C));