F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Passage

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1762    Accepted Submission(s): 958


Problem Description
Bill is a millionaire. But unfortunately he was trapped in a castle. There are only n passages to go out. For any passage i (1<=i<=n), Pi (0<=Pi<=1) denotes the probability that Bill will escape from this castle safely if he chose this passage. Qi (0<=Qi<=1-Pi) denotes the probability that there is a group of guards in this passage. And Bill should give them one million dollars and go back. Otherwise, he will be killed. The probability of this passage had a dead end is 1-Pi-Qi. In this case Bill has to go back. Whenever he came back, he can choose another passage.
We already know that Bill has M million dollars. Help Bill to find out the probability that he can escape from this castle if he chose the optimal strategy.
 

Input
The first line contains an integer T (T<=100) indicating the number of test cases.
The first line of each test case contains two integers n (1<=n<=1000) and M (0<=M<=10).
Then n lines follows, each line contains two float number Pi and Qi.
 

Output
For each test case, print the case number and the answer in a single line.
The answer should be rounded to five digits after the decimal point.
Follow the format of the sample output.
 

Sample Input
3 1 10 0.5 0 2 0 0.3 0.4 0.4 0.5 3 0 0.333 0.234 0.353 0.453 0.342 0.532
 

Sample Output
Case 1: 0.50000 Case 2: 0.43000 Case 3: 0.51458
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-22 16:53:06, Gzip enabled