Overview

A problem where you calculate the refund amount for each visitor based on their ticket type, then find the total.

Analysis

In this problem, refunds are issued according to the following rules based on the ticket type:

• normal (regular ticket): Refund the full purchase amount
• half (student discount ticket): Refund half the purchase amount (rounded down)

Therefore, for each visitor, we simply check the ticket type and add the corresponding refund amount to a running total.

A straightforward approach works without any special tricks, and processing the input as it is read in is sufficiently fast. In languages like Python, using the integer division operator // naturally handles the “round down” operation.

Additionally, from the constraints, \(N\) is at most \(2 \times 10^5\) and \(P_i\) is at most \(10^5\), so the total refund amount is at most around \(2 \times 10^{10}\), which is well within the range of a signed 64-bit integer type (such as long long).

Algorithm

1. Initialize a variable total_refund to \(0\) to hold the total refund amount.
2. For each visitor, do the following:
   • Read the ticket type \(T_i\) and purchase amount \(P_i\).
   • If \(T_i\) is normal, add \(P_i\) to total_refund.
   • If \(T_i\) is half, add \(\left\lfloor \frac{P_i}{2} \right\rfloor\) to total_refund (in Python, P_i // 2).
3. Output the final value of total_refund.

Example

Given the following input:

3
normal 1000
half 800
half 500

The refund amounts are, in order:

• Visitor 1: 1000 yen (normal → full refund)
• Visitor 2: 400 yen (half → half price: 800 ÷ 2 = 400)
• Visitor 3: 250 yen (half → half price: 500 ÷ 2 = 250)

The total is \(1000 + 400 + 250 = 1650\) yen.

Complexity

• Time complexity: \(O(N)\)
  Since we perform constant-time operations for each visitor.
• Space complexity: \(O(1)\)
  The memory required beyond storing the input is constant.

Implementation Notes

• When comparing strings, make sure to write them exactly as 'normal' or 'half'.

• Using integer division (//) automatically handles rounding down.

• The total can become quite large, so depending on the language, be careful about overflow (in Python, this is not a concern).

  Source Code

N = int(input())
total_refund = 0

for _ in range(N):
    T, P = input().split()
    P = int(P)
    
    if T == 'normal':
        total_refund += P
    else:  # T == 'half'
        total_refund += P // 2

print(total_refund)

---

This editorial was generated by qwen3-coder-480b.