概要

フリーマーケットでの各取引において、売上金を受け取り、その半分を手数料として支払った後の所持金をシミュレーションする問題。

考察

この問題では、\(M\) 人のお客さんによる取引が順番に与えられ、それぞれの取引に対して「売上金を得て、その半分を手数料として支払う」という操作を行う必要があります。

重要な観察点は以下の通りです： - 各取引で得られる純利益は「売上金 \(-\) 手数料」であり、売上金が \(X\) のとき、手数料は \(\lfloor X / 2 \rfloor\) となる。 - よって、各取引ごとに「売上金の半分（切り捨て）だけ実際に手に入れる」と考えることができる。 - 例えば、100円の売上が発生した場合、まず100円を受け取り、その場で50円を手数料として支払い、結果として50円だけ増える。

このようにして、各取引を順番に処理していけば良いので、特に複雑なアルゴリズムは必要なく、素直にシミュレーションすれば解けます。

制約を見ると、\(N\) や \(M\) が最大で \(10^5\) となっており、全探索などを行わなければ間に合う範囲です。また、一度も商品リストを変更したり再計算したりする必要がないため、単純な配列アクセスで十分です。

アルゴリズム

1. 商品価格リスト \(P\) を読み込む。
2. 初期所持金 \(S\) を設定する。
3. 各お客さんについて以下の処理を行う：
   • 購入された商品の価格 \(P_{T_j - 1}\)（0-indexedにするため）と個数 \(Q_j\) から売上金 \(sales = P_{T_j - 1} \times Q_j\) を求める。
   • 手数料 \(fee = \lfloor sales / 2 \rfloor\) を計算する。
   • 純利益 \(gain = sales - fee\) を所持金に加算する。
4. 全ての取引が終わったら最終的な所持金を出力する。

計算量

• 時間計算量: \(O(N + M)\)
  （商品価格の読み込みに \(O(N)\)、各取引の処理に \(O(M)\)）
• 空間計算量: \(O(N)\)
  （商品価格を保存する配列のサイズ）

実装のポイント

• 商品番号が1始まりなので、配列のインデックスとしては T - 1 を使う必要がある。
• 売上金の半分を切り捨てる際は、整数除算演算子 // を使うことで自然に処理できる。
• 初期所持金 \(S\) は変更されないので、ループ外で一度だけ読み込めばよい。

## ソースコード

```python
# 入力読み込み
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)

この解説は qwen3-coder-480b によって生成されました。