Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Simple Distributed storage system
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 2106Accepted: 382


Jack helps his mentor build a simple distributed storage system. He uses several servers and connects them as the following topology:

This distributed storage system contains a group of backend servers and a master server. The backend servers are different from each other while they store identical data, and all of them are invisible to client. When a client machine needs a file, it sends request to a master server. The master server collects different part of the file from some of backend servers. The strategy of the master is like follows.

Each backend server has its own processing throughput and transmission bandwidth. The master server knows that ith backend server’s throughput is pi (MB/s) and bandwidth is bi (MB/s). As the result, omitted the propagation time, handling size of fi MB data and sending to master machine needs time:

Total time = Processing time + Transmission time = fi / pi + fi / bi

In addition, handling 1 MB data on ith server costs ci. (Including electricity consumption and maintenance cost, etc.) In order to minimize the total cost, the master server should carefully decide which backends should be used and how much load they should process. At the same time, because of some consistency consideration, every time the master should choose exactly K backend servers to extract file, and each of them should take exactly the same time to finish the job.

Your task is to write a scheduling program for the master server. Assuming the size of the file is F MB, and the file can be infinitely divided.


The first line contains two integers N and K (KN ≤ 20000), and a real number F. The master should choose exactly K machines among total N backend servers. The F is the size of the file.

The following N lines describe the details of each backend servers. Each line contains three real numbers, pi, bi and ci, representing the processing throughput, bandwidth and unit cost.


The output file contains only one real number, the minimum cost. The answer is less than 10000000000 and should be rounded to four digits

Sample Input

3 2 2
1 1 2
1 1 1
2 2 10

Sample Output



In the sample case, the master should choose the first two backend machines. Each of them should handle 1 MB part of the file (total is 2 MB) in order to make the finishing time identically (2 second). The total cost is 1*2+1*1 = 3.0000


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator