Overview

This problem asks you to compute the total time for an entire journey by adding the sum of travel times across \(N\) segments and the “rest time” that occurs according to specific rules.

Analysis

The total time to be calculated is the sum of the following two components: 1. Total travel time: The sum of travel times for all segments \(A_1 + A_2 + \cdots + A_N\) 2. Total rest time: The total number of rest breaks (1 hour each) that occur according to the rules

Counting the Number of Rest Breaks

Rest breaks occur “immediately after finishing a segment whose number is a multiple of \(K\),” but with the condition that “there are still remaining segments to travel.” In other words, rest breaks are taken after segment \(K\), segment \(2K\), …, but no rest break is taken after finishing the last segment \(N\).

Let’s consider some concrete examples: - When \(N=5, K=2\): Rest breaks occur after segment 2 and segment 4. Segment 6 does not exist, so there are 2 rest breaks in total. - When \(N=6, K=2\): Rest breaks occur after segment 2 and segment 4. Segment 6 is the last one, so no rest break is taken after it. There are 2 rest breaks in total.

As we can see, rest breaks occur at timings \(K, 2K, 3K, \dots\) that are less than \(N\). Expressed as a formula, the number of rest breaks equals the quotient (rounded down) when dividing \((N-1)\) by \(K\), i.e., \(\lfloor (N-1) / K \rfloor\).

Algorithm

1. Read \(N, K\) and the travel time \(A_i\) for each segment from input.
2. Compute the total travel time \(S = \sum_{i=1}^{N} A_i\).
3. Compute the number of rest breaks \(R = \lfloor (N-1) / K \rfloor\).
4. Output \(S + R\) as the answer.

Complexity

• Time complexity: \(O(N)\)
  • This is because we need to iterate over \(N\) elements to compute the total travel time. The rest break count can be computed in \(O(1)\).
• Space complexity: \(O(N)\)
  • If the input values \(A_i\) are stored in a list or similar structure, memory proportional to the number of elements is required.

Implementation Notes

• Handling large numbers: Since \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the total time can reach approximately \(2 \times 10^{14}\). In Python, there is no limit on integer size, but when using other languages (such as C++ or Java), you need to use 64-bit integer types (long long or long).

• Computing the number of rest breaks: If you use n // k, when \(N\) is a multiple of \(K\), it will incorrectly count a rest break after the last segment as well. By always using (n - 1) // k, you can correctly compute the number of breaks excluding the last segment.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを取得し、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 区間の数, K: 休憩を挟む間隔
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 各区間の走行時間の合計を計算します
    # map関数を使用して文字列のリストを整数のイテレータに変換し、sumで合計します
    total_travel_time = sum(map(int, input_data[2:2+n]))
    
    # 休憩の回数を計算します
    # 番号がKの倍数である区間のうち、最後の区間（第N区間）を除いたものの個数です
    # これは (n - 1) // k で求めることができます
    num_rests = (n - 1) // k
    
    # 合計時間（走行時間 + 休憩時間）を出力します
    # 休憩1回につき1時間なので、休憩時間は num_rests と等しくなります
    print(total_travel_time + num_rests)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.