Overview

This is a problem where you manage the maximum number of requests each counter can handle, process applications in order, and count how many applications are successfully accepted.

Analysis

Essence of the Problem

This problem is a simple simulation where you just need to manage “how many more requests can be processed” for each counter.

Key Observations

1. Applications are processed in order: Earlier applications have priority
2. Counters are independent: The remaining capacity of counter \(i\) does not affect other counters
3. Managing remaining capacity: It is sufficient to track the value obtained by subtracting the number of accepted requests from the maximum capacity \(C_i\) for each counter

Why a Simple Approach Works

For each application, only two operations are performed: - Check the remaining capacity of the requested counter (\(O(1)\)) - If there is remaining capacity, decrement by 1 and accept the application (\(O(1)\))

Even when performing this process for all \(M\) applications, the total time complexity is only \(O(M)\).

Algorithm

1. Initialization: Prepare an array remaining initialized with \(C_i\) as the remaining processing capacity for each counter \(i\)

2. Processing Applications: Process all \(M\) applications in order

   • Read the requested counter number \(T_j\) for application \(j\)
   • If the remaining capacity of counter \(T_j\) is at least \(1\):
     • Decrement the remaining capacity by \(1\)
     • Increment the accepted count by \(1\)
   • If the remaining capacity is \(0\), do nothing (the application is rejected)

3. Output Result: Output the total number of accepted applications

Concrete Example

When \(N = 2\), \(M = 4\), \(C = [2, 1]\), and applications come for counters \(1, 1, 2, 1\) in that order:

Application	Requested Counter	Counter 1 Remaining	Counter 2 Remaining	Result
Initial	-	2	1	-
1	1	2→1	1	Accepted
2	1	1→0	1	Accepted
3	2	0	1→0	Accepted
4	1	0	0	Rejected

Result: 3 applications accepted

Complexity

• Time Complexity: \(O(N + M)\)
  • Initialization takes \(O(N)\)
  • Processing each application takes \(O(1)\) × \(M\) applications = \(O(M)\)
• Space Complexity: \(O(N)\)
  • The array remaining for managing remaining capacity takes \(O(N)\)

Implementation Notes

1. Index Conversion: In the problem statement, counter numbers start from \(1\) (1-indexed), but Python arrays start from \(0\) (0-indexed), so conversion with idx = T - 1 is necessary

2. Copying the Array: remaining = C[:] copies the list. If you write remaining = C, it becomes a reference assignment, and the original \(C\) would also be modified, so be careful

3. Handling Large \(C_i\): \(C_i\) can be up to \(10^9\), but since we simply store it as the remaining capacity, no special handling is needed

Source Code

def main():
    N, M = map(int, input().split())
    C = list(map(int, input().split()))
    
    # Manage the remaining processing capacity for each counter
    remaining = C[:]
    
    accepted = 0
    
    for _ in range(M):
        T = int(input())
        # Counter numbers are 1-indexed
        idx = T - 1
        if remaining[idx] > 0:
            remaining[idx] -= 1
            accepted += 1
    
    print(accepted)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.