首页 > ACM题库 > UVA > Uva-11722-Joining with Friend-[连续概率]
2013
12-11

Uva-11722-Joining with Friend-[连续概率]

Joining with Friend

You are going from Dhaka to Chittagong by train and you came to know one of your old friends is going from city Chittagong to Sylhet. You also know that both the trains will have a stoppage at junction Akhaura at almost same time. You wanted to see your friend there. But the system of the country is not that good. The times of reaching to Akhaura for both trains are not fixed. In fact your train can reach in any time within the interval [t1, t2] with equal probability. The other one will reach in any time within the interval [s1, s2] with equal probability. Each of the trains will stop for w minutes after reaching the junction. You can only see your friend, if in some time both of the trains is present in the station. Find the probability that you can see your friend.

Input
The first line of input will denote the number of cases T (T < 500). Each of the following T line will contain 5 integers t1, t2, s1, s2, w (360 ≤ t1 < t2 < 1080, 360 ≤ s1 < s2 < 1080 and 1 ≤ w ≤ 90). All inputs t1, t2, s1, s2 and w are given in minutes and t1, t2, s1, s2 are minutes since midnight 00:00.

Output
For each test case print one line of output in the format “Case #k: p” Here k is the case number and p is the probability of seeing your friend. Up to 1e-6 error in your output will be acceptable.

Sample Input
2
1000 1040 1000 1040 20
720 750 730 760 16
Output for Sample Input

Case #1: 0.75000000

Case #2: 0.67111111

在[S1,S2]到达,B在[T1,T2]到达,到达后都会等W分钟,问相遇的概率。

概率论课本上的题目了,列出三个方程s1<=S<=s2,t1<=T<=t2,|T-S|<=w。然后可以转化为几何图形求面积,需要讨论求解。

#include <string.h>
#include <stdio.h>
int cas, t1, t2, s1, s2, w;
double area(int w){
    int lc = t1+w, rc = t2+w, uc = s2-w, dc = s1-w;
    if (lc >= s2) return 0;
    if (rc <= s1) return (t2-t1)*(s2-s1);
    bool bl = (lc>=s1 && lc<=s2);
    bool br = (rc>=s1 && rc<=s2);
    bool bu = (uc>=t1 && uc<=t2);
    bool bd = (dc>=t1 && dc<=t2);
    if (bl&&bu) return (lc-s2)*(lc-s2)*0.5;
    if (bl&&br) return (t2-t1)*(s2-lc+s2-rc)*0.5;
    if (bd&&bu) return (s2-s1)*(uc-t1+dc-t1)*0.5;
    if (bd&&br) return (t2-t1)*(s2-s1)-(rc-s1)*(rc-s1)*0.5;
    return 0;
}
int main(){
    scanf("%d", &cas);
    for (int ca = 1; ca <= cas; ca++) {
        scanf("%d%d%d%d%d", &t1, &t2, &s1, &s2, &w);
        printf("Case #%d: %.7f\n", ca, (area(-w)-area(w))/(t2-t1)/(s2-s1));
    }
    return 0;
}

转自:http://www.cnblogs.com/swm8023/archive/2012/10/29/2745175.html


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确