新規
編集
添付
時間制限: 1000MS
メモリ制限: 65536K
問題文 
ジャックは先生が簡単な分散記憶装置を構築するのを手伝うことになった。彼はいくつかのサーバを次の図のように繋いだ。
この分散記憶装置はいくつかのバックエンドサーバと1つのマスターサーバから成っている。バックエンドサーバは全て同じデータを保持しており、クライアントにはその存在が隠蔽されている。クライアントはファイルが欲しいときにマスターサーバへリクエストを送信する。マスターサーバはいくつかのバックエンドサーバからそれぞれファイルの断片を収集する。そのときマスターサーバのとる方法は以下のようなものである。
それぞれのバックエンドサーバにはそのスループットと帯域幅が決まっている。マスターサーバはi番目のバックエンドサーバのスループットが pi (MB/s) であり帯域幅が bi (MB/s) であることを知っている。ファイルそのものに関する情報などのやり取りを除けば、サイズが fi MB であるデータをバックエンドサーバからマスターサーバへ送信するのに必要な時間は
総時間 = 処理時間 + 通信時間 = fi / pi + fi / bi
によって計算できる。
さらに、i番目のサーバで1MBのデータの扱うのに ci だけのコスト(電気代やメンテナンス費など)がかかる。コストを最小限にするために、マスターサーバはどのバックエンドサーバを使うか、またあるバックエンドサーバにどれだけのデータ量を担当させるかを注意深く決めねばならない。また同時に、ある堅牢性のための理由から、マスターサーバはちょうどK個のバックエンドサーバを選択せねばならず、それぞれのバックエンドサーバが完全に同時にそのジョブを終えるようにしなければならない。
あなたの仕事はマスターサーバのスケジューリング用プログラムを書くことである。要求されるファイルの大きさは F MB であり、ファイルは無限に細かく分割することができるものとする。
入力
入力の1行目は2つの整数 N, K (K <= N <= 20000) および1つの実数 F からなる。これはマスターサーバが全部でN個あるバックエンドサーバからK個を選択せねばならず、また要求されるファイルの大きさが F MB であることを示している。
続くN行にはそれぞれのバックエンドサーバの情報が書かれている。各行には3つの実数 pi, bi, ci が書かれており、これらはそれぞれスループット、帯域幅、単位コストを表す。
出力
出力は最小のコストを表す実数からなる。答は 10000000000 より小さく、小数第5位を四捨五入した値でなければならない。
入力例
3 2 2 1 1 2 1 1 1 2 2 10
出力例
3.0000
ヒント
入出力例ではマスターサーバは最初の2つのバックエンドサーバを選ぶとよい。それぞれにファイルを 1MB ずつ、合計 2MB 担当させれば両方とも同時にそのジョブを終える(この場合は2秒)。またその時のコストの合計は 1*2 + 1+1 = 3.0000 である。
出典
POJ Monthly Contest - 2010.04.04, Yao Jinyu
