Pro.ID22308 TitleThe Brick Stops Here Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22308 AC0 Submit0 Ratio- 时间&空间限制描述You have been hired by several clients of a factory that manufactures brass bricks. Brass is an alloy of copper and zinc; each brick weighs 1000 grams, and the copper content of a brick can range from 1 to 999 grams. (Note that brass with less than 55% or more than 62% of copper is practically useless; however, this is irrelevant for this question) The factory manufactures, through various processes, different types of brick, each of which has a different copper concentration and price. It distributes a catalog of these types to its customers. Your clients desire to buy a certain number (M) of bricks, which for, uh, religious reasons must be of different types. They will be melted together, and the resultant mixture must have a concentration of at least CMin and at most CMax grams of copper per kilogram. Their goal is to pick the M types of brick so that the mixture has the correct concentration and the price of the collection is minimized. You must figure out how to do this. M, CMin, and CMax will vary depending on the client. 输入The first part of input consists of a line containing a number N (1 <= N <= 200), the number of brick types, and then N lines containing the copper concentration (between 1 and 999) and price (in cents) of each brick type. No brick costs more than 10 dollars. The second part consists of a line containing a number C (1 <= C <= 100), the number of clients you are serving, followed by C lines containing M (1 <= M <= 20), CMin (1 <= CMin <= 999), and CMax (1 <= CMax <= 999) for each client. All input numbers will be positive integers. 输出Description You have been hired by several clients of a factory that manufactures brass bricks. Brass is an alloy of copper and zinc; each brick weighs 1000 grams, and the copper content of a brick can range from 1 to 999 grams. (Note that brass with less than 55% or more than 62% of copper is practically useless; however, this is irrelevant for this question) The factory manufactures, through various processes, different types of brick, each of which has a different copper concentration and price. It distributes a catalog of these types to its customers. Your clients desire to buy a certain number (M) of bricks, which for, uh, religious reasons must be of different types. They will be melted together, and the resultant mixture must have a concentration of at least CMin and at most CMax grams of copper per kilogram. Their goal is to pick the M types of brick so that the mixture has the correct concentration and the price of the collection is minimized. You must figure out how to do this. M, CMin, and CMax will vary depending on the client. Input The first part of input consists of a line containing a number N (1 <= N <= 200), the number of brick types, and then N lines containing the copper concentration (between 1 and 999) and price (in cents) of each brick type. No brick costs more than 10 dollars. The second part consists of a line containing a number C (1 <= C <= 100), the number of clients you are serving, followed by C lines containing M (1 <= M <= 20), CMin (1 <= CMin <= 999), and CMax (1 <= CMax <= 999) for each client. All input numbers will be positive integers. Output Output consists of a line for each client containing the minimum possible price for which they can purchase bricks to meet their demands. If there is no way to match their specifications, output "impossible". Sample Input 11 550 300 550 200 700 340 300 140 600 780 930 785 730 280 678 420 999 900 485 390 888 800 3 2 500 620 9 550 590 9 610 620 Sample Output 420 impossible 3635 Source 样例输入11 550 300 550 200 700 340 300 140 600 780 930 785 730 280 678 420 999 900 485 390 888 800 3 2 500 620 9 550 590 9 610 620 样例输出420 impossible 3635 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-4 21:54 , Processed in 0.033842 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
