Xenia and Ringroad

Xenia and Ringroad
Codeforces easy

A ring road has \(n\) houses, numbered \(1\) to \(n\) clockwise. Traffic is one-way: it goes only clockwise, from house \(i\) to house \(i + 1\), and from house \(n\) to house \(1\). Moving to the next house takes one unit of time.

Xenia starts at house \(1\) and has \(m\) tasks. To complete task \(i\), she must be at house \(a_i\), and she must complete the tasks in the given order. Find the minimum time to complete all tasks.

Constraints:

  • \(2 \le n \le 10^5\)
  • \(1 \le m \le 10^5\)
  • \(1 \le a_i \le n\)

Input:

  • First line: two integers \(n\) and \(m\).
  • Second line: \(m\) integers \(a_1, a_2, \ldots, a_m\).

Output:

  • One integer — the minimum time.

Examples:

Input:

4 3
3 2 3

Output:

6

(Xenia moves \(1 \to 2 \to 3\), then \(3 \to 4 \to 1 \to 2\), then \(2 \to 3\): \(2 + 3 + 1 = 6\) units.)

Input:

4 3
2 3 3

Output:

2
Solution

We simulate the walk. We keep the house current where Xenia is now, and for each task we add the time to reach house \(a\):

  • if \(a \ge current\), she walks clockwise without passing house \(n\): \(a - current\) units;
  • if \(a < current\), she walks to house \(n\), then one step to house \(1\), then on to house \(a\): \(n - current + a\) units.

Then \(a\) becomes the new current.

Each task can take almost \(n\) units, so the total time can be almost \(10^5 \cdot 10^5 = 10^{10}\). This does not fit in int, so we store it in long long.

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    long long time = 0;  // can be up to about 10^10
    int current = 1;

    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;

        if (a >= current) {
            time += a - current;
        } else {
            time += n - current + a;  // go past house n and around to house a
        }
        current = a;
    }

    cout << time << "\n";
}