|Online Judge||Problem Set||Authors||Online Contests||User|
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
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 input 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.
The first line of the output 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.
3 300 350 380 100 100 200 100 440 450 100
1.000 2 1 3
Northeastern Europe 2002, Western Subregion
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator