Overview

This problem asks you to calculate the refund amount for each visitor based on their ticket type (full refund or half price rounded down), then find the total.

Analysis

The refund amount is determined independently for each visitor.

• If normal, add the purchase price \(P_i\) as is
• If half, add \(\left\lfloor \dfrac{P_i}{2} \right\rfloor\) (integer division)

Therefore, it is sufficient to read each visitor’s data in order and accumulate the total.

Concrete examples: - normal 100 → \(100\) - half 101 → \(101/2=50.5\), so rounding down gives \(50\) The total becomes \(150\).

Since the constraint is \(N \le 2 \times 10^5\), which is large, an implementation that reads one line at a time with input() will often be fast enough, but in Python it may be slow depending on the environment. Therefore, in the submitted code, we use sys.stdin.buffer.read() to read all input at once for speed, reducing the risk of TLE.

Algorithm

1. Read \(N\) from input
2. Repeat the following for \(N\) people:
   • Read ticket type \(T_i\) and price \(P_i\)
   • If \(T_i=\texttt{normal}\), then total += P_i
   • If \(T_i=\texttt{half}\), then total += P_i // 2
3. Output total

The key point is that “half price (rounded down)” corresponds to Python’s integer division //.

Complexity

• Time complexity: \(O(N)\) (each visitor is processed exactly once)
• Space complexity: \(O(1)\) (only a constant number of variables such as the total)
  • However, since the implementation reads all input at once, the actual memory usage is proportional to the input size.

Implementation Notes

• For “half price rounded down”, use p // 2 (using p / 2 would produce a floating-point number, which is inappropriate)

• Using sys.stdin.buffer.read().split() for fast input allows stable high-speed processing even when \(N\) is large

• Since read().split() returns bytes, we use decode() to convert to strings for comparing ticket types

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    total = 0
    idx = 1
    for _ in range(n):
        t = data[idx].decode()
        p = int(data[idx + 1])
        if t == "normal":
            total += p
        else:  # "half"
            total += p // 2
        idx += 2
    print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.