Overview

This is a problem where \(N\) cars are guided in order based on their preferred parking space \(P_i\), and we simulate how many cars are able to park in the end.

Analysis

The key point of this problem is determining “which space each car can park in” according to the rules each time a car arrives.

The rules can be summarized as follows: 1. First, check the preferred space \(P_i\). 2. If \(P_i\) is occupied, search for an empty space in increasing order: \(P_i + 1\), then \(P_i + 2 \dots\), and so on toward higher-numbered spaces. 3. If no empty space is found even after checking up to space \(M\), the car gives up and leaves.

Looking at the constraints, both the number of cars \(N\) and the number of parking spaces \(M\) are at most 100, which is very small. Therefore, even if we perform a “naive simulation” that checks parking spaces one by one each time a car arrives, the total number of operations is at most \(N \times M = 10,000\). This is sufficiently small compared to the number of operations a typical programming language can handle in 1 second (approximately \(10^8\)), so we can solve this with simple loops.

Algorithm

We perform the simulation with the following steps:

1. Preparation: Prepare an array occupied to manage the state of parking spaces. Initially, all spaces are set to “empty”.
2. Simulation: For each of the \(N\) cars, process them in arrival order as follows:
   • Check spaces sequentially from the car’s preferred space \(P_i\) up to space \(M\).
   • If an empty space \(j\) is found:
     • Update occupied[j] to “parked”.
     • Increment the count of successfully parked cars by \(1\).
     • Move on to processing the next car (end the search for this car).
   • If no empty space is found after checking all the way to the end, ignore that car and move on to processing the next car.
3. Output: Output the final count of successfully parked cars.

Complexity

• Time Complexity: \(O(NM)\)
  • For each of the \(N\) cars, we scan up to \(M\) spaces.
• Space Complexity: \(O(M)\)
  • This is the size of the array needed to store the state (empty or not) of the parking spaces.

Implementation Tips

• Handling 1-indexed: In the problem statement, parking spaces are numbered from \(1\) to \(M\). Since arrays (lists) in programs typically start from \(0\), allocating size \(M+1\) and using indices \(1\) through \(M\) directly helps avoid confusion during implementation.

• Flag management: To determine “whether each car was able to park,” it is convenient to use break in the inner loop or to prepare a variable (such as found) to record whether an empty space was found.

  Source Code

import sys

def main():
    # 入力を取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    m = int(input_data[1])
    p = list(map(int, input_data[2:]))
    
    # 駐車スペースの状態を管理するリスト（1番からM番まで）
    # False: 空き、True: 駐車済み
    occupied = [False] * (m + 1)
    
    parked_count = 0
    
    # 到着順に車を案内する
    for desired_space in p:
        # 希望のスペースから順に、空いている最も番号が小さいスペースを探す
        found = False
        for j in range(desired_space, m + 1):
            if not occupied[j]:
                occupied[j] = True
                parked_count += 1
                found = True
                break
        
        # 条件を満たすスペースがない場合は何もしない（帰ってしまう）
        if not found:
            continue
            
    # 駐車できた台数を出力
    print(parked_count)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-preview.