Overview

This is a problem where trees are lined up in a row, and you repeat the pattern “harvest \(K\) trees → skip \(1\) tree” from left to right, then find the total number of apples harvested.

Analysis

The key point of this problem is that Takahashi’s action pattern is completely determined. Takahashi has no freedom of choice and mechanically repeats the following starting from tree \(1\):

1. Harvest from \(K\) consecutive trees
2. Skip \(1\) tree

In other words, one cycle consists of every \((K+1)\) trees, and only the last \(1\) tree of each cycle is skipped.

Let’s verify with concrete examples:

• When \(N = 7, K = 3\): The cycle length is \(K+1 = 4\)

  • Cycle 1: Trees \(1, 2, 3\) (harvest) → Tree \(4\) (skip)
  • Cycle 2: Trees \(5, 6, 7\) (harvest) → Tree \(8\) does not exist, so we stop
  • Harvested trees: \(1, 2, 3, 5, 6, 7\)

• When \(N = 8, K = 2\): The cycle length is \(K+1 = 3\)

  • Cycle 1: Trees \(1, 2\) (harvest) → Tree \(3\) (skip)
  • Cycle 2: Trees \(4, 5\) (harvest) → Tree \(6\) (skip)
  • Cycle 3: Trees \(7, 8\) (harvest) → Tree \(9\) does not exist, so we stop
  • Harvested trees: \(1, 2, 4, 5, 7, 8\)

Since whether each tree is harvested or skipped is uniquely determined in this way, the problem can be solved by simply simulating the process.

The straightforward approach itself is sufficiently fast, as we look at each tree at most once, running in \(O(N)\). No special algorithm is needed.

Algorithm

Starting with index \(i\) at \(0\), repeat the following:

1. Harvest phase: Repeat \(K\) times, adding \(D[i]\) to the total and incrementing \(i\) by \(1\). If \(i \geq N\), stop.
2. Skip phase: Increment \(i\) by \(1\) (skip \(1\) tree).

Repeat this until \(i \geq N\), then output the total.

i = 0, total = 0
while i < N:
    Add D[i] to total for K trees, advancing i (while i < N)
    Increment i by 1 (skip)

Complexity

• Time complexity: \(O(N)\) (since each tree is processed at most once)
• Space complexity: \(O(N)\) (for the array storing the number of apples)

Implementation Notes

• Do not forget to check \(i < N\) inside the harvest phase. There are cases where tree \(N\) is reached in the middle of harvesting \(K\) trees (the case where the process ends in the middle of a pattern).

• No boundary check is needed in the skip phase. Even if \(i\) becomes \(N\) or greater, the loop will terminate at the next while i < N condition.

• Since \(D_i\) can be up to \(10^9\) and \(N\) can be up to \(10^6\), the total value can be up to approximately \(10^{15}\). In Python there is no integer overflow so this is not an issue, but in C++ and similar languages, you need to use long long.

  Source Code

N, K = map(int, input().split())
D = list(map(int, input().split()))

total = 0
i = 0
while i < N:
    # Harvest K trees
    for j in range(K):
        if i < N:
            total += D[i]
            i += 1
        else:
            break
    # Skip 1 tree
    i += 1

print(total)

---

This editorial was generated by claude4.6opus-thinking.