ABC 26 D - 高橋君ボール1号 ( Binary search + EPS )

D: 高橋君ボール1号 - AtCoder Beginner Contest 026 | AtCoder
精度が怖い。

出力するものがたとえ1e-10の誤差だけあったとしても関数が出るものに1e-5ぐらい影響がまだるので、ちゃんと限界まで行かないとやばい。

#include <bits/stdc++.h>
using namespace std;
const int MAXABC = 100 + 2;
const double PI = acos( -1.0 );
const double EPS = 1e-10; // why cannot 1e-7??

int a, b, c;

double func(double x){
    return x * a + sin( x * c * PI ) * b;
}

void solve(){
    double lb = 0.0, ub = 1e9;
    while( true ){
        double mid = ( lb + ub ) / 2;
        if( fabs( func( mid ) - 100.0 ) < EPS ) break;
        if( func( mid ) < 100.0 )
            lb = mid;
        else
            ub = mid;
    }
    printf("%.12lf\n", lb);
}

int main(){
    scanf("%d%d%d", &a, &b, &c);
    solve();
    return 0;
}

こんな書き方の方がいいと思う。実行の時間制限ギリギリまで精度を調整する方が楽。

#include <bits/stdc++.h>
using namespace std;
const int MAXABC = 100 + 2;
const double PI = acos( -1.0 );

int a, b, c;

double func(double x){
    return x * a + sin( x * c * PI ) * b;
}

void solve(){
    double lb = 0.0, ub = 1e9;
    for(int i = 0; i < 200000; ++i){
        double mid = ( lb + ub ) / 2;
        if( func( mid ) < 100.0 )
            lb = mid;
        else
            ub = mid;
    }
    printf("%.12lf\n", lb);
}

int main(){
    scanf("%d%d%d", &a, &b, &c);
    solve();
    return 0;
}