ABC 026 D - 高橋君ボール1号
問題概要
省略
解法
2分探索でとく。関数はだいたい増加しているような関数であるので、解をもつ範囲の左端をL、右端をR、真ん中をM とすると、t=Mの時に、関数の値が100を超えるなら、中間地の定理より(あたりまえ)、左側の部分に解を必ず一つはもつ。100より小さいなら、増加していく関数なので、右側の範囲に解をもつことになる。このような考えて、2分探索を実装すればいい。
問題に与えられている、 |f(t)−100|<=10-6は関数の値の誤差のことなので、tはもっと厳密に出さないといけないのかな?
最後を%.9fだとWAになった。
ミス
誤差はうまく扱うのが難しいなー。 tの最小値ならどう出すんだ?
コード
再帰関数
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) double a, b, c; double f(double t){ return a * t + b * sin(c * t * M_PI); } int main(void){ cin >> a >> b >> c; double l = -1000.0, r = 1000.0; rep(i, 10000){//十分な回数を回す double mid = (l + r) / 2.0; // 真ん中で100より小さいなら、真ん中より右側にこたえがある if(f(mid) < 100.0) l = mid; //真ん中で100より大きいなら、中間値の定理より、左側に必ずf=100となるtが存在する else r = mid; } printf("%.12f\n", l); }