程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDOJ 3232 Crossing Rivers 簡單概率

HDOJ 3232 Crossing Rivers 簡單概率

編輯：C++入門知識

HDOJ 3232 Crossing Rivers 簡單概率

簡單期望:

船到岸邊時間的期望是 L/v 再過河的時間是L/v

所以過每條河的時間期望是2*L/v

Crossing Rivers

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 699 Accepted Submission(s): 361

Problem Description You live in a village but work in another village. You decided to follow the straight path between your house (A) and the working place (B), but there are several rivers you need to cross. Assume B is to the right of A, and all the rivers lie between them.

Fortunately, there is one "automatic" boat moving smoothly in each river. When you arrive the left bank of a river, just wait for the boat, then go with it. You're so slim that carrying you does not change the speed of any boat.

Days and days after, you came up with the following question: assume each boat is independently placed at random at time 0, what is the expected time to reach B from A? Your walking speed is always 1.

To be more precise, for a river of length L, the distance of the boat (which could be regarded as a mathematical point) to the left bank at time 0 is uniformly chosenfrom interval [0, L], and the boat is equally like to be moving left or right, if it’s not precisely at the river bank.
Input There will be at most 10 test cases. Each case begins with two integers n and D, where n (0 <= n <= 10) is the number of rivers between A and B, D (1 <= D <= 1000) is the distance from A to B. Each of the following n lines describes a river with 3 integers: p, L and v (0 <= p < D, 0 < L <= D, 1 <= v <= 100). p is the distance from A to the left bank of this river, L is the length of this river, v is the speed of the boat on this river. It is guaranteed that rivers lie between A and B, and they don’t overlap. The last test case is followed by n=D=0, which should not be processed.
Output For each test case, print the case number and the expected time, rounded to 3 digits after the decimal point.

Print a blank line after the output of each test case.
Sample Input

Sample Output

Case 1: 1.000

Case 2: 1.000

Source 2009 Asia Wuhan Regional Contest Hosted by Wuhan University

/* ***********************************************
Author        :CKboss
Created Time  :2015年01月29日 星期四 16時39分29秒
File Name     :UVA12230.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int n,d;
struct River
{
	int p,l,v;
}ri[20];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	int cas=1;
	while(scanf("%d%d",&n,&d)!=EOF)
	{
		if(n==0&&d==0) break;
		double ans1=0.0;
		double sum=0.0;
		for(int i=0;i