AOJ : 1225 - e-market

問題概要

函館市は, 最近商品取引市場を設立した.
市場に参加するために, ディーラは, 「自分の名前」「売買のタイプ」「商品の名前」「見積もり価格」をインターネットに送信する.

このマーケットでは, 売却の価格が購入の価格以下である場合のみ, 取引が行われる.
取引の価格は, 購入価格と売却価格の平均をとり, 小数点以下は切り捨てる.
不正な取引をなくすために, 同じディーラからの売却＆購入のペアは, 取引を行わない.
市場のシステムは, 注文のリストを次のルールに従い, 新しい注文を処理する.

• 新しい売却の注文のとき
  • 取引は, 一番高額の購入の注文と行われる.
  • もし, そのような注文が複数あるのならば, 取引時間が一番早い注文が採用される.
• 新しい購入の注文のとき
  • 取引は, 一番低額の売却の注文と行われる.
  • もし, そのような注文が複数あるのならば, 取引時間が一番早い注文が採用される.

各商品が取引されるときの, 最小の額と, 平均の額, 最大の額を求めよ.
また, 各ディーラが支払った額と, 受け取った額を求めよ.

アルゴリズム

書くだけ.

購入注文と, 売却注文を, 別々のリストにしておいて

• 購入注文の方は, 常に購入金額の降順に
• 売却注文の方は, 常に売却金額の昇順に

な感じにしておく.

各注文に対して, 今まで出てきた注文を順番に見ていく.
取引が適用できる注文があれば, それと取引したことにする.
取引したやつは, リストから取り除く.