Overview

Given \(N\) visitors, calculate the refund amount based on the ticket type (normal or half) for each visitor, and find the total.

Analysis

For each visitor, we need to calculate the refund amount according to the following rules specified in the problem statement: - If the ticket is normal: Refund the full purchase price \(P_i\). - If the ticket is half: Refund half the purchase price \(\lfloor P_i / 2 \rfloor\) (rounded down).

The key points for solving this problem are as follows: 1. Conditional branching: Read the ticket type as a string and use an if statement to perform the appropriate calculation based on the type. 2. Rounding down: The “half (rounded down)” calculation can be achieved without any special handling by using integer division between integers in the programming language. 3. Size of the total: Since \(N\) can be up to \(2 \times 10^5\) and each \(P_i\) can be up to \(10^5\), the total refund amount can reach approximately \(2 \times 10^{10}\). Python natively handles arbitrarily large integers (arbitrary-precision integers), so even when the value exceeds the range of a typical 32-bit integer (approximately \(2 \times 10^9\)), calculations can be performed without worrying about overflow.

Algorithm

1. Initialize a variable total_refund to \(0\) to hold the total refund amount.
2. Read the number of visitors \(N\).
3. For each visitor \(i = 1, 2, \dots, N\), repeat the following process:
   • Obtain the ticket type \(T_i\) and the price \(P_i\).
   • If \(T_i\) is normal, add \(P_i\) to total_refund.
   • If \(T_i\) is half, add \(P_i // 2\) (integer division) to total_refund.
4. Output the final value of total_refund.

Complexity

• Time complexity: \(O(N)\)
  • Since we process each of the \(N\) visitors’ data once in order, the computation completes in time proportional to the number of visitors.
• Space complexity: \(O(N)\)
  • In this implementation, we use sys.stdin.read().split() to read all input data into memory at once, so the memory usage is proportional to the input size.

Implementation Notes

• Fast I/O: Since \(N\) can be large, instead of calling the input() function \(N\) times, using sys.stdin.read().split() to read all input at once and process it as a list can significantly reduce execution time.

• Integer division operator: In Python, using / produces a floating-point number (float type), but using // directly yields an integer (int type) with the fractional part truncated. This avoids floating-point precision issues.

  Source Code

import sys

def main():
    # 入力を一括で読み込み、空白文字で分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 最初の要素は人数 N
    n = int(input_data[0])
    total_refund = 0
    
    # 各来場者のデータを処理
    for i in range(n):
        # チケットの種類 T_i と購入金額 P_i を取得
        t = input_data[1 + 2 * i]
        p = int(input_data[2 + 2 * i])
        
        if t == 'normal':
            # 一般チケットは全額払い戻し
            total_refund += p
        elif t == 'half':
            # 学割チケットは半額（端数切り捨て）を払い戻し
            total_refund += p // 2
            
    # 合計金額を出力
    print(total_refund)

if __name__ == '__main__':
    main()

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