UVa 1555 - Garland

contents

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

Problem

給定 N 盞燈，第一盞燈的所在高度 A。

• Hi = (Hi-1 + Hi+1)/2 - 1

在 Hi 不低於地面高度 0 的條件下，請問最後一盞燈的高度最低為何。

Sample Input

692 532.81

Sample Output

446113.34

Solution

二分搜尋第二盞燈的高度，推算出所有燈的高度，必且找最小高度。

#include <stdio.h>

double isValid(int N, double H1, double H2) {
    double H = 0;
    for (int i = 3; i <= N; i++) {
        H = 2 * H2 + 2 - H1;
        if (H < 0)	return -1;
        H1 = H2;
        H2 = H;
    }
    return H;
}
int main() {
    int N;
    double A;
    while (scanf("%d %lf", &N, &A) == 2) {
        double l = 0, r = A, mid, ret = 0, t;
        for (int it = 0; it < 50; it++) {
            mid = (l + r)/2;
            if ((t = isValid(N, A, mid)) >= 0)
                r = mid, ret = t;
            else
                l = mid;
        }
        printf("%.2lf\n", ret);
    }
    return 0;
}