PKU 1759 Garland
http://poj.org/problem?id=1759
小数aと整数nが与えられる。
ここで
H_1=a
H_i=(H_i-1+H_i+1)/2-1 (1=0 (1<=i<=n)
を満たすような数列のうち、h_nの最小値を求めるというような問題。
微妙に不吉なAC数(444)を通り越しました。
h_2について条件をみたしているかを確認しながら二分探索しました。
小数の二分探索のほうが整数よりごちゃごちゃ考えなくていいので考えつければ楽な気がします。
上限が結構大きいようで適当に設定したら最初サンプルが通らなかったので、適当に設定しても通るか微妙な気がしましたが何とか一発AC。
main(){ int n; double a; cin>>n>>a; double u=1LL<<32,l=0; double ans=1LL<<32; while(abs(u-l)>EPS){ double mid=(u+l)/2; bool ok=true; double hi_m1=a,hi=mid; rep(i,n-2){ double hi_p1=2*hi+2-hi_m1; if(hi_p1<0){ ok=false; break; } if(i==n-3)ans=min(ans,hi_p1); hi_m1=hi; hi=hi_p1; } if(ok)u=mid; else l=mid; } printf("%.2f\n",ans); }