Overview

This problem asks for the minimum total fatigue required to deliver a specified number of letters to each point located along a straight line, starting from point \(1\) (the post office). At first glance, it might seem like we need to consider complex combinations, such as how many trips to make. However, by focusing on the minimum fatigue required per letter, we can solve the problem with a very simple mathematical formula.

Analysis

1. Minimum fatigue required per letter

Let us focus on a single letter addressed to point \(i\) (\(2 \leq i \leq N\)). To successfully deliver this letter to its destination, it must be carried from point \(1\) to point \(i\) at least once.

Between point \(1\) and point \(i\), there are \((i-1)\) intervals between adjacent points (\([1, 2], [2, 3], \ldots, [i-1, i]\)). To deliver the letter, it must pass through each of these intervals at least once. Since passing through an interval once incurs \(1\) unit of fatigue, the fatigue generated to deliver a single letter addressed to point \(i\) is at least \(i-1\), regardless of the route taken.

Therefore, the total fatigue required to deliver all letters cannot be smaller than the following lower bound, no matter how we optimize the delivery route: $\(\sum_{i=2}^{N} B_i \times (i - 1)\)$

2. Verification of whether the lower bound can be achieved

Now, does a delivery route actually exist that achieves this lower bound of \(\sum_{i=2}^{N} B_i \times (i - 1)\)?

In fact, we can achieve this lower bound exactly by adopting a simple strategy: “Start the very first trip carrying all the letters together, and deliver all the letters addressed to each point as we pass by it.”

With this strategy, the letters addressed to point \(i\) are carried from point \(1\) to point \(i\) without ever backtracking. Thus, the number of times they pass through each interval \([p, p+1]\) (\(p < i\)) is exactly \(1\), meaning the fatigue generated by each of these letters is precisely \(i-1\).

Concrete Example (\(N=3, B_2=2, B_3=3\))

• There are \(2\) letters addressed to point \(2\) (each requiring a minimum fatigue of \(2-1 = 1\)).
• There are \(3\) letters addressed to point \(3\) (each requiring a minimum fatigue of \(3-1 = 2\)).
• The theoretical minimum fatigue (lower bound) is \(2 \times 1 + 3 \times 2 = 8\).

Simulation of starting with all letters (5 in total): 1. Departure: Depart from point \(1\) carrying \(5\) letters. 2. Move \(1 \to 2\): Since we have \(5\) letters in hand, \(5\) fatigue is generated. Arrive at point \(2\) and deliver \(2\) letters addressed to point \(2\) (leaving \(3\) letters in hand). 3. Move \(2 \to 3\): Since we have \(3\) letters in hand, \(3\) fatigue is generated. Arrive at point \(3\) and deliver \(3\) letters addressed to point \(3\) (leaving \(0\) letters in hand). 4. Return: Fatigue for the return trip is \(0\).

The total fatigue generated is \(5 + 3 = 8\), which matches the theoretical lower bound.

Therefore, the minimum value we want to find is always \(\sum_{i=2}^{N} B_i \times (i - 1)\).

Algorithm

1. Initialize a variable total_fatigue representing the total fatigue to \(0\).
2. For \(i = 2, 3, \ldots, N\), read the inputs sequentially.
3. For the number of letters \(B_i\) at point \(i\), calculate B_i * (i - 1) and add it to total_fatigue.
4. Output the final value of total_fatigue.

Complexity

• Time Complexity: \(O(N)\)
  Since we iterate through the information of each point once to perform the calculation, the algorithm runs in linear time with respect to the number of points \(N\).
• Space Complexity: \(O(1)\)
  By processing and summing up the inputs on the fly without storing them in an array, the calculation can be done without using extra memory.

Implementation Notes

• Preventing Overflow:
  \(N\) is at most \(10^6\), and each \(B_i\) is at most \(10^7\).
  The maximum possible answer is approximately \(\sum_{i=2}^{10^6} 10^7 \times i \approx 10^7 \times \frac{(10^6)^2}{2} \approx 5 \times 10^{18}\), which significantly exceeds the maximum value of a standard 32-bit integer type (int, which is about \(2 \times 10^9\)). Therefore, make sure to use a 64-bit integer type (such as long long in C++) for both calculations and storing the answer.

• Fast I/O:
  Since \(N\) can be as large as \(10^6\), you can significantly reduce the execution time in C++ by using std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); to speed up input and output.

  Source Code

#include <iostream>

using namespace std;

int main() {
    // Optimize input/output operations for speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    long long total_fatigue = 0;
    for (int i = 2; i <= N; ++i) {
        long long B;
        cin >> B;
        total_fatigue += B * (i - 1);
    }

    cout << total_fatigue << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.