12584 - Laptop Chargers

发布时间:2014-10-22 12:09:19编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"12584 - Laptop Chargers",主要涉及到12584 - Laptop Chargers方面的内容,对于12584 - Laptop Chargers感兴趣的同学可以参考一下。

ABC has set many problems for programming contests but has bought even more laptops in his life. Fortunately, all his laptops are still working but some of his chargers are not working. If he has Nlaptops: (i) Minimum how many chargers does he need to run all the laptops forever?  (ii) Maximum how long will he be able to run all his laptops using M (M < N) chargers? You need to assume the following things for simplicity: (i) The battery of each laptop has a charge capacity C (Expressed in mAh)  (ii) The battery discharge amount is always strictly linear with time (eg: It looses fixed mAh charge in every second) and the fully charged battery of the laptop completely discharges in time T (Expressed in seconds)  (iii) The charge that the charger adds with the battery of a laptop is always linear with time as well.  (iv) All chargers are identical and any laptop is compatible with any charger.  (v) The charging rate of a charger is strictly greater than discharging rate of any laptop.  (vi) Zero time is needed to shift a charger from one laptop to another. If needed this shifting can be done indefinite amount of times.  (vii) Exactly one charger can be used to charge a laptop. Input  The input file contains around 1000 sets of input. The description of each set is given below. Each test case starts with two integer N ( 0 < N < 101) and Q ( 0 < Q10). Here N is the total number of laptops owned by ABC and Q is the total no of query. The 2nd line describes the chargers (All chargers are identical). This line contains an integer Chps ( 1Chps3) which denotes the amount of charge (expressed in mAh) the charger adds with the battery in a second. Each of the next N lines describes the status of one laptop. Each laptop is described with three integers C, T and R. Here C ( 2000C10000) is the capacity of Battery (Expressed in mAh), T ( 3000T28800) is the time required for the fully charged battery to discharge (Expressed in seconds), R ( 0 < RC) is the charge remaining in the laptop battery (Expressed in mAh) at the beginning. Each of the next Q lines contains an integer M which describes number of chargers ABC has in his possession. Input is terminated by a line containing two zeroes. Output  For each set of input you should produce Q + 2 lines of outputs. First line is the serial of output and second line contains an integer Mmin which denotes minimum how many charges are needed to run all the laptops indefinitely. You can assume that input will be such that small precision error will not change the value of Mmin. Each of the next Q lines contains a floating-point number T (rounded to three digits after the decimal point) which denotes maximum how long (In seconds) the N laptops can run with M chargers. But if with M chargers the laptops run more than 100000 seconds output `-1.000' instead. Look at the output for sample input for details. For the value of T, an absolute error of less than 0.02 will be ignored. Sample Input  4 2 2 3269 6150 3117 4135 5839 2770 3377 5552 779 7452 17787 2924 2 2 0 0 Sample Output  Case 1: 2 -1.000 -1.000

下一篇:50个jQuery Mobile开发技巧