Pro.ID22685 TitleRPG Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22685 AC0 Submit0 Ratio- 时间&空间限制描述To complete a role-playing game (RPG), you must send your character through N quests. The quests may be passed in any order, but after starting a quest you can’t drop it and switch to another. If your character fails even one quest you fail the whole game. The probability of succeeding in a quest depends on the experience points (XP) of your character at the beginning of the quest, and is determined by the formula
whereai and bi are parameters of the i-th quest. After successful completion of the i-th quest, your character obtains Si experience points. Initially, it/he/she has D points. Write a program to determine such an order of the quests that the probability of completing the whole game successfully is the highest possible.输入The first line of the file contains the values N ( 1 <= N <= 10 ) and D. Each of the following N lines describes one quest, containing the values ai, bi, Si. The values D, ai, bi, Si ( 1 <= i <= N ) are all integers in the range from 0 to 1000 and ai<bi ( 1 <= i <= N ). Adjacent values on the same line are separated by one or more spaces. 输出Description To complete a role-playing game (RPG), you must send your character through N quests. The quests may be passed in any order, but after starting a quest you can’t drop it and switch to another. If your character fails even one quest you fail the whole game. The probability of succeeding in a quest depends on the experience points (XP) of your character at the beginning of the quest, and is determined by the formula
whereai and bi are parameters of the i-th quest. After successful completion of the i-th quest, your character obtains Si experience points. Initially, it/he/she has D points. Write a program to determine such an order of the quests that the probability of completing the whole game successfully is the highest possible.Input The first line of the file contains the values N ( 1 <= N <= 10 ) and D. Each of the following N lines describes one quest, containing the values ai, bi, Si. The values D, ai, bi, Si ( 1 <= i <= N ) are all integers in the range from 0 to 1000 and ai<bi ( 1 <= i <= N ). Adjacent values on the same line are separated by one or more spaces. Output The first line must contain the highest possible probability with the precision of 0.001. The second line must contain the order of quests that ensures this probability. If there are several orders with the same probability, output any one of them. Sample Input 3 300
350 380 100
100 200 100
440 450 100 Sample Output 1.000
2 1 3 Hint Special Judge Source 样例输入3 300
350 380 100
100 200 100
440 450 100 样例输出1.000
2 1 3 提示Special Judge |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-5 16:43 , Processed in 0.037321 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
