Algoogle

Algorithm for Programming Contest

PKU 1759 Garland

Category: PKU Tag: binary-search

Garland

問題概要


解法


H2を決めればBが一意に決まる.
基本的にH2を小さくすればBも小さくなるのでH2を二分探索する.
判定部分は途中のHが負になる場合は失敗, それ以外は成功.

####


(1759.cpp) download
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
#include <iostream>
using namespace std;
#define rep(i,a) for(int i = 0;i < (a); i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)

int N;
double A, B;
double H[1024];

bool ok(double h){
    H[1] = h;
    repi(i,2,N){
	H[i] = 2*H[i-1] + 2 - H[i-2];
	if(H[i] < 0) return false;
    }
    B = H[N-1];
    return true;
}

int main(){
    cin >> N >> A;
    H[0] = A;
    double lb = -1, ub = 1000000;
    rep(_,100){
        double mid = (lb + ub) / 2;
        if(ok(mid)) ub = mid;
        else lb = mid;
    }
    printf("%.2f\n", B);
    return 0;
}

Comments