Pro.ID22322 TitleOld Wine Into New Bottles Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22322 AC1 Submit2 Ratio50.00% 时间&空间限制描述 Wine bottles are never completely filled: a small amount of air must be left in the neck to allow for thermal expansion and contraction. If too little air is left in the bottle, the wine may expand and expel the cork; if too much air is left in the bottle, the wine may spoil. Thus each bottle has a minimum and maximum capacity. Given a certain amount of wine and a selection of bottles of various sizes, determine which bottles to use so that each is filled to between its minimum and maximum capacity and so that as much wine as possible is bottled. 输入The first line of input contains two integers: the amount of wine to be bottled (in litres, between 0 and 1,000,000) and the number of sizes of bottles (between 1 and 100). For each size of bottle, one line of input follows giving the minimum and maximum capacity of each bottle in millilitres. The maximum capacity is not less than 325 ml and does not exceed 4500 ml. The minimum capacity is not less than 95% and not greater than 99% of the maximum capacity. You may assume that an unlimited number of each bottle is available. 输出Description Wine bottles are never completely filled: a small amount of air must be left in the neck to allow for thermal expansion and contraction. If too little air is left in the bottle, the wine may expand and expel the cork; if too much air is left in the bottle, the wine may spoil. Thus each bottle has a minimum and maximum capacity. Given a certain amount of wine and a selection of bottles of various sizes, determine which bottles to use so that each is filled to between its minimum and maximum capacity and so that as much wine as possible is bottled. Input The first line of input contains two integers: the amount of wine to be bottled (in litres, between 0 and 1,000,000) and the number of sizes of bottles (between 1 and 100). For each size of bottle, one line of input follows giving the minimum and maximum capacity of each bottle in millilitres. The maximum capacity is not less than 325 ml and does not exceed 4500 ml. The minimum capacity is not less than 95% and not greater than 99% of the maximum capacity. You may assume that an unlimited number of each bottle is available. Output Your output should consist of a single integer: the amount of wine, in ml, that cannot be bottled. Sample Input Sample (1) 10 2
Sample (2) 10000 2 Sample Output Sample (1) 250
0 Source 样例输入Sample (1) 10 2
Sample (2) 10000 2 样例输出Sample (1) 250
0 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-4 23:58 , Processed in 0.037938 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
