Overview

This problem asks for the maximum number of groups (carts) when dividing consecutive packages into groups such that each group has equal weight.

Analysis

Key Insight ①: The number of carts must be a divisor of the total weight

When using \(k\) carts, each cart’s weight becomes \(\frac{\text{total weight}}{k}\). Since this must be an integer for equal division to be possible, the number of carts \(k\) must be a divisor of the total weight.

Key Insight ②: Greedy partitioning works

Once the target weight for each cart is determined, we can use a greedy approach: scan packages from left to right, and whenever the cumulative sum reaches the target weight, make a cut there.

For example, with \(H = [2, 1, 3, 2, 4]\) (total weight \(12\)): - When \(k = 4\), target weight is \(3\) - \(2 + 1 = 3\) ✓ (1st cart) - \(3 = 3\) ✓ (2nd cart) - After \(2\), \(2 + 4 = 6 > 3\), failure ✗ - When \(k = 3\), target weight is \(4\) - \(2 + 1 = 3 < 4\), \(2 + 1 + 3 = 6 > 4\), failure ✗ - When \(k = 2\), target weight is \(6\) - \(2 + 1 + 3 = 6\) ✓ (1st cart) - \(2 + 4 = 6\) ✓ (2nd cart) - Success! The answer is \(2\)

Issues with the Naive Approach

Trying all partition patterns leads to exponential time complexity. However, since we only need to check divisors, and each divisor can be verified in \(O(N)\) time, the problem can be solved efficiently.

Algorithm

1. Enumerate all divisors of the total weight

   • Check from \(1\) to \(\sqrt{\text{total weight}}\) and list all divisor pairs

2. Sort divisors in descending order

   • Since we want to maximize the number of carts, try larger divisors first

3. For each divisor \(k\), check if partitioning is possible

   • Target weight \(= \frac{\text{total weight}}{k}\)
   • Add packages from left to right:
     • If cumulative sum equals target weight, one cart is complete (reset cumulative sum)
     • If cumulative sum exceeds target weight, fail
   • If exactly \(k\) carts are formed after scanning all packages, success

4. Output the first successful \(k\)

Complexity

• Time Complexity: \(O(\sqrt{S} + d(S) \cdot N)\)

  • \(S\) is the total weight, \(d(S)\) is the number of divisors of \(S\)
  • Enumerating divisors takes \(O(\sqrt{S})\)
  • Verification for each divisor takes \(O(N)\)
  • The number of divisors is at most a few thousand even for \(S \leq 2 \times 10^{14}\), so this is fast enough

• Space Complexity: \(O(N + d(S))\)

  • Storage for the input array and divisor list

Implementation Notes

• Divisor enumeration: Search in the range \(i \times i \leq \text{total}\), adding both \(i\) and \(\frac{\text{total}}{i}\) (being careful about duplicates)
• Termination condition for verification: After the loop, confirm that current == 0 and count == k
• Worst case guarantee: \(k = 1\) (loading everything onto one cart) always succeeds, so there is never a case with no answer

Source Code

def solve():
    N = int(input())
    H = list(map(int, input().split()))
    
    total = sum(H)
    
    # Calculate prefix sum
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + H[i]
    
    # Try number of carts k from largest to smallest
    # k must be a divisor of the total sum
    # Each cart's weight is total / k
    
    # Enumerate divisors of the total sum
    divisors = []
    i = 1
    while i * i <= total:
        if total % i == 0:
            divisors.append(i)
            if i != total // i:
                divisors.append(total // i)
        i += 1
    
    # Sort divisors in descending order (try larger cart counts first)
    divisors.sort(reverse=True)
    
    for k in divisors:
        # Weight for each cart
        target = total // k
        
        # Check if we can form target using consecutive packages
        count = 0
        current = 0
        possible = True
        
        for i in range(N):
            current += H[i]
            if current == target:
                count += 1
                current = 0
            elif current > target:
                possible = False
                break
        
        if possible and current == 0 and count == k:
            print(k)
            return
    
    # At minimum, all packages can be loaded onto one cart
    print(1)

solve()

---

This editorial was generated by claude4.5opus.