Overview

This is a problem where we need to find the total number of apples harvested when Takahashi collects apples following a predetermined pattern.

Analysis

In the problem, Takahashi repeats a pattern of harvesting apples from \(K\) consecutive trees, then skipping the next 1 tree. This pattern starts from tree 1 and continues until tree N is reached. As a straightforward approach, we can manage the current position with a while loop, adding the apples from \(K\) trees at each step and skipping one tree, efficiently computing the total sum. Since the input size can be up to \(10^6\), even a simple simulation can handle it in \(O(N)\).

Algorithm

1. Initialize the current position idx to 0 (0-indexed).
2. While idx is less than \(N\), repeat the following:
   • Add the number of apples from \(K\) trees starting from the current position (or all remaining trees if fewer than \(K\) remain) to the total sum.
   • Advance the current position by \(K\) trees, then skip 1 more tree (idx = end + 1).
3. Output the total sum.

Complexity

• Time complexity: \(O(N)\)
  • Because each apple is added at most once.
• Space complexity: \(O(N)\)
  • Because the array storing the number of apples has size \(N\).

Implementation Notes

• Since arrays are handled with 0-indexing, the initial position is set to 0.

• min(idx + K, N) concisely handles the case where fewer than \(K\) trees remain.

• Since additions are performed directly within the loop, the implementation is simple without using any extra data structures.

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    N = int(data[0])
    K = int(data[1])
    D = list(map(int, data[2:2+N]))
    
    total = 0
    idx = 0
    while idx < N:
        end = min(idx + K, N)
        for i in range(idx, end):
            total += D[i]
        idx = end + 1
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.