Overview

This is a problem where you need to determine the final amount of money after \(M\) transactions at a flea market with \(N\) types of products. Since half of the sales amount (rounded down) is deducted as a fee for each transaction, you need to perform the calculation precisely for each individual transaction.

Analysis

The key points for solving this problem are the following three:

1. Per-transaction calculation: The fee is charged “per transaction,” not on the “total sales.” For example, if there are two sales of 5 yen each, each transaction incurs a fee of \(\lfloor 5/2 \rfloor = 2\) yen, and the amount remaining is \((5-2) + (5-2) = 6\) yen. If you calculate this at once on the total sales of 10 yen, the fee would be \(\lfloor 10/2 \rfloor = 5\) yen, giving a different result. You need to simulate exactly as instructed in the problem statement: “paid on the spot” and “processed in order.”

2. Constraints and computational complexity: The number of product types \(N\) and the number of customers \(M\) are at most \(10^5\). Since each transaction can be computed in constant time \(O(1)\), the overall complexity is \(O(M)\). This is well within the time limit.

3. Fast input: In Python, calling input() \(M\) times can be slow when the number of input lines is large. By reading all input at once using sys.stdin.read().split(), processing can be done much faster.

Algorithm

The simulation is performed with the following steps:

1. Store the initial amount of money \(S\) in a variable (e.g., current_cash).
2. Store the prices of each product \(P_1, P_2, \ldots, P_N\) in an array (list). Note that product numbers start from 1, but arrays in most programming languages start from 0, so be careful with indexing (the price of product \(T_j\) is P[T_j - 1]).
3. For each transaction \((T_j, Q_j)\), repeat the following calculation \(M\) times:
   • Calculate the sales amount for that transaction: \(X = P_{T_j} \times Q_j\).
   • Calculate the fee: \(F = \lfloor X / 2 \rfloor\).
   • Add \((X - F)\) to the current cash.
4. Output the final amount of money.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading product prices takes \(O(N)\), and processing transactions takes \(O(M)\).
• Space complexity: \(O(N + M)\)
  • The array holding product prices uses \(O(N)\), and if all input is read at once, \(O(N + M)\) memory is used.

Implementation Notes

• Integer division: In Python, using the // operator easily performs integer division with truncation toward negative infinity (floor function \(\lfloor \cdot \rfloor\)).

• 1-indexed vs 0-indexed: When using “\(T_j\)-th product” from the problem statement as an array index, you need to subtract 1 to get P[T_j - 1].

• Large numbers: The final amount of money can be as large as approximately \(10^9 + (10^5 \times 10^4 \times 10^4) = 10^{13}\), but since Python natively supports arbitrary-precision integers, there is no need to worry about overflow.

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストに格納します
    # この方法は大量の入力を高速に処理するのに適しています
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 1行目のデータ（N: 商品の種類数, M: お客さんの人数, S: 初期の所持金）をパースします
    N = int(input_data[0])
    M = int(input_data[1])
    S = int(input_data[2])
    
    # 2行目のデータ（各商品の価格 P_1, P_2, ..., P_N）をパースします
    # 商品番号は1から始まりますが、リストの添字として扱うために0-indexedで管理します
    P = list(map(int, input_data[3:3+N]))
    
    # 現在の所持金を管理する変数（初期値は S 円）
    current_cash = S
    
    # 3行目以降の購入情報（T_j: 購入した商品の種類, Q_j: 購入個数）を順番に処理します
    # 購入情報は input_data の 3+N 番目の要素から始まります
    idx = 3 + N
    for _ in range(M):
        # 商品の種類 T_j と個数 Q_j を取得
        t_j = int(input_data[idx])
        q_j = int(input_data[idx+1])
        idx += 2
        
        # その取引での売上金額 X を計算します
        # T_j は1から始まるため、リスト P の添字は t_j - 1 となります
        sales = P[t_j - 1] * q_j
        
        # 手数料は売上の半分（小数点以下切り捨て）です
        # 最終的な手元の増加分は「売上 - 手数料」となります
        # Pythonの // 演算子は小数点以下切り捨ての整数除算を行います
        fee = sales // 2
        current_cash += (sales - fee)
        
    # すべての取引完了後の所持金を出力します
    print(current_cash)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-thinking.