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;
}
/*
*/