Overview

A problem where you simulate the amount of money held after receiving sales revenue and paying half of it as a commission fee for each transaction at a flea market.

Analysis

In this problem, transactions by \(M\) customers are given in order, and for each transaction, you need to perform the operation of “receiving sales revenue and paying half of it as a commission fee.”

The key observations are as follows: - The net profit from each transaction is “sales revenue \(-\) commission fee,” and when the sales revenue is \(X\), the commission fee is \(\lfloor X / 2 \rfloor\). - Therefore, for each transaction, you can think of it as “actually receiving only half of the sales revenue (rounded down).” - For example, if a sale of 100 yen occurs, you first receive 100 yen, immediately pay 50 yen as a commission fee, and as a result, your money increases by only 50 yen.

Since you just need to process each transaction in order, no particularly complex algorithm is needed, and the problem can be solved with a straightforward simulation.

Looking at the constraints, \(N\) and \(M\) are at most \(10^5\), which is within a feasible range as long as you don’t perform brute-force enumeration. Also, since there is no need to modify or recalculate the product list, simple array access is sufficient.

Algorithm

1. Read the product price list \(P\).
2. Set the initial amount of money \(S\).
3. For each customer, perform the following operations:
   • Compute the sales revenue \(sales = P_{T_j - 1} \times Q_j\) from the price \(P_{T_j - 1}\) of the purchased product (subtracting 1 for 0-indexed) and the quantity \(Q_j\).
   • Calculate the commission fee \(fee = \lfloor sales / 2 \rfloor\).
   • Add the net profit \(gain = sales - fee\) to the current amount of money.
4. After all transactions are completed, output the final amount of money.

Complexity

• Time complexity: \(O(N + M)\)
  (\(O(N)\) for reading product prices, \(O(M)\) for processing each transaction)
• Space complexity: \(O(N)\)
  (size of the array storing product prices)

Implementation Notes

• Since product numbers are 1-indexed, you need to use T - 1 as the array index.

• When taking the floor of half the sales revenue, the integer division operator // handles this naturally.

• Since the initial amount of money \(S\) does not change, it only needs to be read once outside the loop.

  Source Code

# 入力読み込み
N, M, S = map(int, input().split())
P = list(map(int, input().split()))

# 所持金の初期化
money = S

# 各取引を順に処理
for _ in range(M):
    T, Q = map(int, input().split())
    # 商品番号は1始まりなのでインデックスはT-1
    price = P[T - 1]
    # 売上金額
    sales = price * Q
    # 手数料（売上の半分を切り捨て）
    fee = sales // 2
    # 実際に手元に残るお金
    gain = sales - fee
    # 所持金に加算
    money += gain

# 最終的な所持金を出力
print(money)

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