Overview

Given the dish names \(T_i\) that \(N\) customers actually ordered and the dish names \(S_i\) that the server communicated to the kitchen, the problem asks how many customers had their orders conveyed incorrectly (i.e., \(T_i\) and \(S_i\) do not match).

Analysis

What this problem requires is checking for every customer \(i\) whether “\(T_i\) equals \(S_i\)”, and counting the number of cases where they are not equal.

The number of customers \(N\) is at most \(10^5\), and the length of each dish name is at most 20 characters, which is short. Therefore, a straightforward approach of checking each customer’s order one by one is more than fast enough.

Specifically, we proceed with the following steps: 1. Initialize a variable count to 0 to track the number of incorrect orders. 2. For each customer from the 1st to the \(N\)-th, repeat the following: - If \(T_i\) differs from \(S_i\) (\(T_i \neq S_i\)), add 1 to count. 3. Output the final value of count.

Algorithm

1. Reading input: Obtain \(N\) and each pair \((T_i, S_i)\).
2. Iteration: Use a loop (for loop) to scan through each customer’s data.
3. Condition check: Use the string comparison operator (!= in Python) to determine whether the order contents match.
4. Aggregation: Record the number of times the condition is satisfied.

Complexity

• Time complexity: \(O(N \times L)\)
  • We check each of the \(N\) customers once, giving \(O(N)\). For each check, string comparison takes time proportional to the dish name length \(L\) (at most 20). Since \(L\) is sufficiently small, the overall execution is very fast.
• Space complexity: \(O(N \times L)\)
  • This is the complexity when storing all input strings in memory.

Implementation Notes

• Fast input: Since \(N\) can be as large as \(10^5\), rather than calling input() repeatedly in Python, using sys.stdin.read().split() to read all input at once is more efficient and reduces execution time.

• String comparison: In Python, you can simply write t != s to easily determine whether the contents of two strings differ.

  Source Code

import sys

def main():
    # 標準入力から全データを取得し、空白・改行で分割する
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 1つ目の要素は人数 N
    n = int(data[0])
    
    count = 0
    # 2つ目以降の要素を T_i, S_i のペアとして処理する
    for i in range(n):
        t = data[2 * i + 1]
        s = data[2 * i + 2]
        # 実際の注文と伝達が異なればカウント
        if t != s:
            count += 1
            
    # 結果を出力
    print(count)

if __name__ == '__main__':
    main()

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