Overview

For each of the \(N\) visitors, calculate the refund amount based on the ticket type, and find the total. For a regular ticket (normal), the full price is refunded; for a student discount ticket (half), half the price (rounded down) is refunded.

Analysis

This problem is very straightforward — you simply need to branch on the condition for each visitor and accumulate the refund amounts.

• Key observation: There are only 2 ticket types, normal and half, so a simple if-else is sufficient.
• Rounding down: For student discount tickets, the refund is half the purchase price, rounded down (floor division). For example, if the purchase price is \(P = 1001\) yen, the refund is \(\lfloor 1001 / 2 \rfloor = 500\) yen. In Python, this can be achieved using the integer floor division operator //.
• No special tricks are needed for this problem — a naive loop over all \(N\) visitors is perfectly sufficient. Since \(N \leq 2 \times 10^5\), an \(O(N)\) solution runs with plenty of room.

Concrete Example

Consider the following input:

3
normal 1000
half 1500
half 1001

The total refund amount is \(1000 + 750 + 500 = 2250\).

Algorithm

1. Read the number of visitors \(N\).
2. Initialize a variable total to \(0\) to track the total amount.
3. Read the data for each of the \(N\) visitors one by one, and perform the following:
   • If the ticket type is normal, add the purchase price \(P_i\) directly to total.
   • If the ticket type is half, add \(\lfloor P_i / 2 \rfloor\) to total.
4. Output the final value of total.

Complexity

• Time complexity: \(O(N)\) — constant-time processing is performed for each visitor.
• Space complexity: \(O(1)\) — only a variable to hold the total amount is used; there is no need to store all the data.

Implementation Notes

• Floor division: In Python, the // operator performs integer floor division. As long as \(P_i\) is a positive integer, p // 2 correctly gives the half price rounded down.

• Parsing input: Each line contains the ticket type (string) and the purchase price (integer) separated by a space, so you can split with input().split() and then convert only the price part to an integer using int().

• Conditional branching: Since the ticket type is either normal or half, it is sufficient to check if t == "normal" and treat everything else as half.

  Source Code

N = int(input())
total = 0
for _ in range(N):
    t, p = input().split()
    p = int(p)
    if t == "normal":
        total += p
    else:
        total += p // 2
print(total)

This editorial was generated by claude4.6opus-thinking.