【UVA12230】过河 Crossing Rivers

UVA12230 过河 Crossing Rivers

题目描述

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.

你住在一个村子里但是在另一个村子工作。你决定沿着你家 $A$ 和工作地点 $B$ 之间的一条直路去上班。但是路上有几条河需要你跨过。假设 $B$ 在 $A$ 的右边,且所有河都位于他们之间。

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.

很多天以后,你想到一些问题:假设每艘船在起始时间时被随机地放置在河中,从 $A$ 到 $B$ 期望时间是多少?你的行走速度始终为 $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 chosen from interval [0, L], and the boat is equally like to be moving left or right, if it’s not precisely at the river bank.

准确地说,对于长度为L的河流,船到左岸的距离为 $[0, L]$ 间的任意数字,并且当船不在河岸时,其向左或向右的概率相等。

输入格式

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.

共有最多 10 个测试样例。每个测试样例由两个整数 $n, D$ 开头。$n\ (0 \le n \le 10)$ 代表 $A$ 与 $B$ 间河流的数量,$D\ (1 \le D \le 1000)$ 为 $A$ 与 $B$ 的距离。接下来 $n$ 行每行用三个整数 $p, L, v\ (0 \le p < D, 0 < L \le D, 1 \le v \le 100)$ 代表一条河流。$p$ 是 $A$ 到这条河左岸的距离,$L$ 是这条河的长度,$v$ 是船在这条河上的速度。数据保证河流都在 $A$ 与 $B$ 之间,且相互不重合。测试样例以 $n = D = 0$ 结束。

输出格式

For each test case, print the case number and the expected time, rounded to 3 digits after the decimal point.

对于每个测试样例,输出样例编号和期望时间,保留3位小数。

Print a blank line after the output of each test case

在每行结果之后输出一个空行。

Solution

过每条河最坏的情况是 $t=3*L/v$,即去的时候船刚刚走。

过每条河最优的情况是 $t=L/v$, 即去的时候船刚刚来。

由于船是均匀发布的,符合线性性质,所以平均下来,过每条河的时间 $t=2*L/v$。

AC Code

#include<cstdio>
typedef long long llint;
const bool DEBUG_ENABLE = 0;
const int MAXN = 1e5 + 5;
const int MOD = 19260827;

int n, d;
int main() {
/*==================================*/
#ifdef LOCAL_JUDGE
    freopen("../in.in", "r", stdin);
    freopen("../out.out", "w", stdout);
#endif
/*==================================*/
    for(int i = 1, tmp = scanf("%d%d", &n, &d); tmp != EOF; ++i, tmp = scanf("%d%d", &n, &d)) {
        if(n == 0 && d==0) break;
        double ans = 0;
        while (n--) {
            int p, l, v;
            scanf("%d%d%d", &p, &l, &v);
            d -= l;
            ans += 2.0 * l / v;
        }
        printf("Case %d: %.3lf\n\n", i, ans + d);
    }
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注