Overview

This problem asks us to find the minimum total fatigue required to deliver letters to various locations aligned on a straight line. At first glance, it might seem to require complex planning, such as “how many trips to divide the delivery into” or “at what timing to distribute them.” However, by focusing on the fatigue generated per letter, we can solve it with a very simple formula.

Analysis

Focusing on a Single Letter

Let’s consider carrying just one letter to be delivered to location \(j\) (\(2 \leq j \leq N\)). To deliver this letter from location \(1\) (the post office) to its destination, location \(j\), we must inevitably pass through the following intervals while carrying this letter: - \(1 \to 2\), \(2 \to 3\), \(\ldots\), \(j-1 \to j\)

When moving through these intervals, since we have this letter in hand, \(1\) unit of fatigue is generated for each interval we advance. Since the distance from location \(1\) to location \(j\) is \(j - 1\), the fatigue generated to deliver this single letter will always be at least \(j - 1\), regardless of how it is carried.

Avoiding Inefficient Movements

If we make inefficient moves, such as carrying the letter to an intermediate location, returning to the post office once, and then carrying it to the destination again on a subsequent route, we would pass through the same interval multiple times while holding that letter. This would make the generated fatigue strictly greater than \(j - 1\).

Therefore, for all letters, the most efficient approach is to “take them out only once and deliver them straight to their destinations.”

How to Achieve the Minimum Value

Consider taking out all letters at the same time for a single trip, and as we proceed through locations \(2, 3, \ldots, N\), we distribute the required number of letters at each destination.

In this case, since every letter is carried only “from the moment of leaving the post office until it arrives at its destination,” no inefficiency like carrying it back midway occurs. As a result, for every letter destined for location \(j\), the generated fatigue can be kept to the minimum value of \(j - 1\).

Therefore, the minimum total fatigue to be found is the sum of the minimum fatigue generated by each letter, which is expressed by the following formula:

\[ \sum_{j=2}^{N} B_j \times (j - 1) \]

Algorithm

1. Receive the number of letters for locations \(2\) to \(N\), \(B_2, B_3, \ldots, B_N\), as input.
2. For each location \(j\), calculate the value of the number of letters \(B_j\) multiplied by the “distance from the post office, \(j - 1\)”.
3. Output the sum of all these calculated values.

Complexity

• Time Complexity: \(O(N)\) Since we perform one multiplication and one addition for each location’s number of letters, the algorithm runs in linear time \(O(N)\) with respect to the number of locations \(N\).
• Space Complexity: \(O(N)\) It uses \(O(N)\) memory to store the input in an array (list).

Implementation Details

Be careful about the discrepancy between the 0-based index in programming and the 1-based actual location numbers.

In the provided code, B stores \(B_2, B_3, \ldots, B_N\). If we use Python’s enumerate(B), the loop variable i will range from \(0, 1, \ldots, N-2\). At this point, the i-th element of the list (b) corresponds to the number of letters destined for location \(j = i + 2\). Since the distance to this location \(j\) is \(j - 1 = i + 1\), we can correctly find the answer by calculating and summing b * (i + 1) in each iteration.

Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    B = list(map(int, input_data[1:]))
    
    ans = sum(b * (i + 1) for i, b in enumerate(B))
    print(ans)

if __name__ == '__main__':
    main()

---

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