Pro.ID10244 TitleWork Reduction Title链接http://10.20.2.8/oj/exercise/problem?problem_id=10244 AC0 Submit0 Ratio- 时间&空间限制描述Paperwork is beginning to pile up on your desk, and tensions at the workplace are starting to mount. Your boss has threatened to fire you if you don't make any progress by the end of the day. You currently have N units of paperwork on your desk, and your boss demands that you have exactly M units of paperwork left by the end of the day. 输入The first line of input consists of a single positive integer representing the number of cases to follow. Each case begins with three positive integers separated by spaces: N - your starting workload, M - your target workload, and L - the number of work reduction agencies available to you, (1 ≤ M ≤ N ≤ 100000, 1 ≤ L ≤ 100). The next L lines have the format "[agency name]:A,B", where A and B are the rates as described above for the given agency. (0 ≤ A, B ≤ 10000) The length of the agency name will be between 1 and 16, and will consist only of capital letters. Agency names will be unique. 输出Description Paperwork is beginning to pile up on your desk, and tensions at the workplace are starting to mount. Your boss has threatened to fire you if you don't make any progress by the end of the day. You currently have N units of paperwork on your desk, and your boss demands that you have exactly M units of paperwork left by the end of the day. Input The first line of input consists of a single positive integer representing the number of cases to follow. Each case begins with three positive integers separated by spaces: N - your starting workload, M - your target workload, and L - the number of work reduction agencies available to you, (1 ≤ M ≤ N ≤ 100000, 1 ≤ L ≤ 100). The next L lines have the format "[agency name]:A,B", where A and B are the rates as described above for the given agency. (0 ≤ A, B ≤ 10000) The length of the agency name will be between 1 and 16, and will consist only of capital letters. Agency names will be unique. Output For each test case, print "Case X", with X being the case number, on a single line, followed by the table of agency names and their respective minimum costs, sorted in non-decreasing order of minimum costs. Sort job agencies with identical minimum costs in alphabetical order by agency name. For each line of the table, print out the agency name, followed by a space, followed by the minimum required cost for that agency to solve your problem. Sample Input 2
100 5 3
A:1,10
B:2,5
C:3,1
1123 1122 5
B:50,300
A:1,1000
C:10,10
D:1,50
E:0,0 Sample Output Case 1
C 7
B 22
A 37
Case 2
E 0
A 1
D 1
C 10
B 50 Source 样例输入2
100 5 3
A:1,10
B:2,5
C:3,1
1123 1122 5
B:50,300
A:1,1000
C:10,10
D:1,50
E:0,0 样例输出Case 1
C 7
B 22
A 37
Case 2
E 0
A 1
D 1
C 10
B 50 作者 |