解題區/解題區 - UVa

UVa 12550 - How do spiders walk on water

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

一個可以行走在靜止水面上的蜘蛛，現在要靠近瀑布，瀑布會於鄰近周圍會產生流速。

蜘蛛最多可以在 P 速度的水面上前進，請問最近可以靠近瀑布多少。現在已知從靜止水面靠近瀑布的部分流速，在未知的部分根據觀察是前面單位距離 1 距離 2 的線性關係。$v_{i} = a v_{i-1} + b v_{i-2}$)

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
3 3 0 1 1 1
10 2 0 1 1 2
10 3 0 1 1 2
10 4 0 1 1 2
10 5 0 1 1 2
10 6 0 1 1 2
10 7 0 1 1 2
10 8 0 1 1 2
10 9 0 1 1 2
10 3 1 1 2 2 2 3 3 3 3 4 4
10 5 1 1 2 2 2 3 3 3 3 4 4
10 5 6 6 6 6 8 8 8 11 30 41 42
10 2 0 1 1 1 1 1 1 1 1 1 1
50 200 0 3 6 15 36

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
The spider may fall!
7
6
6
5
5
5
4
4
2
The spider may fall!
The spider is going to fall!
The spider may fall!
45

Solution

其實這題不難，在最後已知得部分解二元一次方程式即可，把未知的流速算出來，統計可以跑多遠即可。

一開始看不懂題目，以為所有流速都是線性關係，求出來的答案怪怪的。從最後已知的四個流速推測剩餘流速。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h> 
#include <algorithm>
#include <sstream> 
#include <iostream>
using namespace std;
char line[1048576];
pair<double, double> solve(double a1, double b1, double c1, double a2, double b2, double c2) {
    // a1 x + b1 y = c1, a2 x + b2 y = c2
    double dx, dy, d;
    d = a1 * b2 - b1 * a2;
    dx = c1 * b2 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return make_pair(dx / d, dy / d);
}
int main() {
    int D, P;
    while (gets(line)) {
        stringstream sin(line);
        sin >> D >> P;
        double d[32767];
        int n = 0;
        while (sin >> d[n])	n++;
        int pos = 0;
        if (n < D + 1) {
            pair<double, double> sol = solve(d[n-4], d[n-3], d[n-2], d[n-3], d[n-2], d[n-1]);
//			printf("%lf %lf\n", sol.first, sol.second);
            for (int i = n; i < D + 1; i++, n++) {
                d[i] = sol.first * d[i-2] + sol.second * d[i-1];
                if (P < d[i])	break;
            }
        }		
        for (int i = 0; i < D + 1; i++) {
            if (P < d[i])	break;
            pos++;
        }
        if (pos == D + 1)
            puts("The spider may fall!");
        else if (pos == 0)
            puts("The spider is going to fall!");
        else
            printf("%d\n", D - pos + 1);
    }
    return 0;
}
/*
*/