Overview

This is a problem where you sell products at a flea market and need to find the final amount of money you have after paying half of the sales (rounded down) as a commission fee for each transaction.

Analysis

The key points of this problem are as follows.

Accurately understanding the flow of each transaction

When the \(j\)-th customer buys \(Q_j\) units of product \(T_j\), the sales amount is \(X = P_{T_j} \times Q_j\) yen. At this point:

1. First, you receive \(X\) yen
2. Immediately after, you pay \(\lfloor X / 2 \rfloor\) yen as a commission fee

In other words, the amount remaining in your hands from one transaction is \(X - \lfloor X / 2 \rfloor\) yen.

Concrete example: If 3 units of a product priced at \(300\) yen are purchased, \(X = 900\) yen. The commission is \(\lfloor 900 / 2 \rfloor = 450\) yen, so the amount remaining is \(900 - 450 = 450\) yen.

If \(X = 7\) yen (odd), the commission is \(\lfloor 7 / 2 \rfloor = 3\) yen, so the amount remaining is \(7 - 3 = 4\) yen. Due to rounding down, when the amount is odd, you keep \(1\) yen more than half of the sales.

A straightforward approach is sufficient

This problem can be solved by simply simulating the \(M\) transactions in order. Since \(M \leq 10^5\), processing each transaction in \(O(1)\) is fast enough. No special algorithm is needed.

Caution: The commission must be calculated for each transaction

Rather than “summing up the total sales from all transactions and then subtracting the commission,” the floor operation \(\lfloor X / 2 \rfloor\) occurs per transaction. Since the number of floor operations differs, computing them all together may yield a different answer.

Algorithm

1. Set the initial amount of money \(S\) to the variable cash.
2. For each of the \(M\) customers, do the following in order:
   • Calculate the sales amount \(X = P_{T_j - 1} \times Q_j\) (since product numbers are 1-indexed, subtract \(-1\) when accessing the array).
   • Add \(X - \lfloor X / 2 \rfloor\) to cash.
3. Output the final value of cash.

Complexity

• Time complexity: \(O(N + M)\) (\(O(N)\) for reading product prices, \(O(M)\) for processing transactions)
• Space complexity: \(O(N)\) (array to store product prices)

Implementation Notes

• Product number \(T_j\) is 1-indexed (starts from 1), so when accessing the array, you need to use P[t - 1].

• For the commission calculation, use integer division (floor division). In Python, the // operator performs floor division for non-negative integers, so x // 2 computes this correctly as-is.

• The maximum value of the sales amount \(X\) is \(P_i \times Q_j \leq 10^4 \times 10^4 = 10^8\), and the maximum amount of money is on the order of \(10^9 + 10^5 \times 10^8\), but since Python has no integer overflow, this is not a concern (in C++ and similar languages, you would need to use long long).

  Source Code

N, M, S = map(int, input().split())
P = list(map(int, input().split()))
cash = S
for _ in range(M):
    t, q = map(int, input().split())
    x = P[t - 1] * q
    cash += x - x // 2
print(cash)

---

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