Overview

This problem involves pouring water into connected buckets and counting the number of buckets that become full in order. Water accumulates starting from bucket 1, and when a bucket becomes full, it overflows into the next bucket.

Analysis

Understanding the Problem

The key point of this problem is to correctly understand how water flows.

• Water flows into bucket 1
• When bucket 1 becomes full, the overflowing water flows into bucket 2
• When bucket 2 becomes full, the overflowing water flows into bucket 3
• This repeats

In other words, water always accumulates in order starting from bucket 1.

Working Through a Concrete Example

For example, with \(N = 3\), \(W = 10\), and capacities \(C = [3, 5, 4]\):

1. First, water accumulates in bucket 1 (capacity 3) → 3 liters used, 7 liters remaining
2. Bucket 1 becomes full, and water overflows into bucket 2 (capacity 5) → 5 liters used, 2 liters remaining
3. Bucket 2 becomes full, and water overflows into bucket 3 (capacity 4) → With only 2 liters remaining, bucket 3 does not become full

Result: 2 buckets became full

Approach

Since water always accumulates in order from the front, we simply need to subtract capacities starting from bucket 1.

• If remaining water \(\geq\) current bucket’s capacity → that bucket becomes full
• If remaining water \(<\) current bucket’s capacity → that bucket does not become full, and processing ends

Since we can solve this in \(O(N)\) by simply checking buckets in order from the front, no special algorithm is required.

Algorithm

1. Initialize remaining water remaining_water to \(W\)
2. Initialize the count of full buckets count to \(0\)
3. Repeat the following for buckets 1 through N in order:
   • If remaining_water >= C[i]:
     • Subtract C[i] from remaining_water
     • Increment count by 1
   • Otherwise:
     • Break out of the loop (no subsequent buckets will become full)
4. Output count

Complexity

• Time complexity: \(O(N)\)
  • In the worst case, we check each bucket once
• Space complexity: \(O(N)\)
  • The size of the array storing bucket capacities

Implementation Notes

1. Watch for overflow: \(W\) can be as large as \(10^{18}\), which is very large, but in Python there’s no need to worry about integer overflow. In C++ and similar languages, you need to use the long long type.

2. Early termination: By using break to exit the loop as soon as a bucket cannot become full, we avoid unnecessary processing (though the order of complexity remains unchanged).

3. Simple implementation: This problem can be solved by straightforward simulation. No complex algorithms are needed—the important thing is to implement exactly what the problem statement describes.

   Source Code

def solve():
    N, W = map(int, input().split())
    C = list(map(int, input().split()))
    
    count = 0
    remaining_water = W
    
    for i in range(N):
        if remaining_water >= C[i]:
            remaining_water -= C[i]
            count += 1
        else:
            break
    
    print(count)

solve()

---

This editorial was generated by claude4.5opus.