Overview

This is a simulation problem where you guide cars into a parking lot in order, searching for empty spaces starting from each car’s preferred space, and counting the number of cars that successfully parked.

Analysis

Understanding the Problem

This problem simulates parking cars in an actual parking lot.

For example, with \(M = 5\) (5 parking spaces) and 3 cars arriving with preferred spaces \([3, 3, 3]\): - Car 1: Space 3 is empty → Parks in space 3 - Car 2: Space 3 is occupied → Searches spaces 4, 5 in order, parks in space 4 - Car 3: Spaces 3, 4 are occupied → Parks in space 5

Result: All 3 cars can park.

Key Observations

1. Order matters: Cars must be processed in arrival order (from car 1 to car N)
2. Search direction is one-way only: Only search for spaces with higher numbers than the preferred space (do not search lower numbers)
3. Once a space is occupied, it stays occupied: Cars do not leave

A Naive Approach is Sufficient

In this problem, the constraints are small with \(N, M \leq 100\), so a naive method of searching for empty spaces sequentially from each car’s preferred space is fast enough.

Algorithm

1. Initialization: Prepare an array available of length \(M+1\), initializing all spaces as “empty” (True) (using 1-indexed for convenience)

2. Process each car in order:

   • Get car \(i\)’s preferred space \(P_i\)
   • Check spaces from \(P_i\) to \(M\) in order
   • Park in the first empty space found (set available[space] = False and increment the counter)
   • If no empty space is found, the car leaves (do nothing)

3. Output result: Print the number of cars that successfully parked

Example Walkthrough

For \(N = 3, M = 4, P = [2, 2, 4]\):

Car	Preferred	Space State [1,2,3,4]	Result
1	2	[○,○,○,○] → [○,×,○,○]	Parks in space 2
2	2	[○,×,○,○] → [○,×,×,○]	Parks in space 3
3	4	[○,×,×,○] → [○,×,×,×]	Parks in space 4

Answer: 3 cars

Complexity

• Time Complexity: \(O(N \times M)\)

  • For each car (\(N\) cars), we search at most \(M\) spaces in the worst case
  • Since \(N, M \leq 100\), this is at most about \(10000\) operations, which is fast enough

• Space Complexity: \(O(M)\)

  • Size of the array recording parking space usage

Implementation Tips

1. Handling 1-indexed: Since parking spaces are numbered from \(1\) to \(M\), creating an array of length M + 1 and not using index \(0\) makes implementation easier

2. Processing successful parking: Once an empty space is found, immediately break and move on to processing the next car (to avoid parking the same car in multiple spaces)

3. Processing failed parking: For cars that couldn’t find an empty space, nothing special needs to be done (just don’t increment the counter)

Source Code

def solve():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    
    # Parking space availability (True means empty)
    available = [True] * (M + 1)  # 1-indexed
    
    parked_count = 0
    
    for i in range(N):
        preferred = P[i]
        
        # Search sequentially from the preferred parking space
        parked = False
        for space in range(preferred, M + 1):
            if available[space]:
                available[space] = False
                parked_count += 1
                parked = True
                break
        
        # If parking failed, the car leaves (do nothing)
    
    print(parked_count)

solve()

---

This editorial was generated by claude4.5opus.