Overview

This problem asks us to find the total amount of water used over \(D\) days, where \(N\) residents take turns watering in cyclic order by their numbers. Since \(D\) can be as large as \(10^{14}\), we need to compute the answer efficiently without simulating day by day.

Analysis

Problem with the Naive Approach

Simulating one day at a time requires \(D\) iterations of a loop. Since \(D\) can be up to \(10^{14}\) (100 trillion), this would far exceed the time limit (TLE).

Key Insight: Periodicity of the Cycle

After cycling through all \(N\) people, the order returns to the beginning. In other words, the same pattern repeats every \(N\) days.

For example, when \(N = 3\), \(S = 2\), \(A = [5, 3, 7]\), the order of duty is:

\[\underbrace{2, 3, 1}_{1\text{st cycle}}, \underbrace{2, 3, 1}_{2\text{nd cycle}}, \underbrace{2, 3, 1}_{3\text{rd cycle}}, \ldots\]

The water amounts follow the pattern \(3, 7, 5, 3, 7, 5, 3, 7, 5, \ldots\), repeating with a period of \(N\) days.

Solution

We split the \(D\) days as follows:

• Number of complete cycles: \(q = \lfloor D / N \rfloor\) (cycles where all \(N\) people serve exactly once)
• Remaining days: \(r = D \bmod N\)

In one complete cycle, everyone serves exactly once, so the total water is \(A_1 + A_2 + \cdots + A_N\). Since this repeats \(q\) times, we can compute it all at once as \(q \times \sum A_i\).

For the remaining \(r\) days, we add the water amounts for \(r\) people starting from position \(S\). Since \(r \leq N - 1 \leq 2 \times 10^5\), processing this with a loop is fast enough.

Algorithm

1. Compute the total sum \(\text{total\_sum} = \sum_{i=1}^{N} A_i\).
2. Find the number of complete cycles \(q = \lfloor D / N \rfloor\) and the remainder \(r = D \bmod N\).
3. Initialize the result as \(\text{result} = q \times \text{total\_sum}\).
4. For the remaining \(r\) days, for \(j = 0, 1, \ldots, r-1\), add the water amount \(A\) of resident number \(((S - 1 + j) \bmod N) + 1\).
5. Output \(\text{result}\).

Concrete Example

For \(N = 3\), \(D = 7\), \(S = 2\), \(A = [5, 3, 7]\):

• \(\text{total\_sum} = 5 + 3 + 7 = 15\)
• \(q = 7 \div 3 = 2\), \(r = 7 \bmod 3 = 1\)
• Complete cycles: \(2 \times 15 = 30\)
• Remaining 1 day: water amount of resident \(2\), \(A_2 = 3\)
• Total: \(30 + 3 = 33\)

Verification: The duty order is residents \(2,3,1,2,3,1,2\) → water amounts \(3+7+5+3+7+5+3 = 33\) ✓

Complexity

• Time complexity: \(O(N)\) (computing the total sum and looping over the remaining days)
• Space complexity: \(O(N)\) (storing the array \(A\))

Implementation Notes

• 0-indexed vs 1-indexed conversion: Resident numbers start from 1, but arrays start from 0, so compute the index as (S - 1 + j) % N.

• Beware of integer overflow: \(D\) can be up to \(10^{14}\) and \(\text{total\_sum}\) can be around \(2 \times 10^9\), so their product can reach approximately \(2 \times 10^{23}\). Python handles arbitrary-precision integers so there is no issue, but in languages like C++, even long long may overflow, so caution is needed.

  Source Code

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

# Reorder A so that the sequence starts from S
# Day j (1-indexed) is handled by person ((S-1+j-1) % N) + 1
# So the sequence of water amounts is A[S-1], A[S%N], A[(S+1)%N], ...

total_sum = sum(A)
full_cycles = D // N
remainder = D % N

result = full_cycles * total_sum

# Add the remainder days
for j in range(remainder):
    idx = (S - 1 + j) % N
    result += A[idx]

print(result)

---

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