傳送門：
Garland
題意：
給出一個函數有幾項和第一項，此函數相鄰３個值必滿足中間值為兩邊平均值減１，且最小值不能為負，求最後一項。
思路：
我們很容易就可以發現可以二分搜最後一項，檢查是否有負值即可，但是要構造出中間的值極為麻煩，所以再繼續觀察一下吧。
接著，我們又發現有函式的第二項即可推出最後一項，較簡單而且也有單調性，所以二分搜第２項來構造函數，一邊維護最後一項的值以及檢查是否有值為負。
code:
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
32
int N;
long double A,B, eps = 1e-9;
void init(){
cin >> N >> A;
}
inline bool suc(long double x2){
long double x1 = A;
for(int i=2;i<N;i++){
long double tmp = x2*2 - x1 + 2;
if(tmp<0) return false;
x1 = x2;
x2 = tmp;
}
B = x2;
return true;
}
void sol(){
#define mid ((L+R)/2)
long double L = -eps, R = A + eps;
for(int i=0;i<50;i++)
suc(mid) ? R = mid : L = mid;
suc(R);
cout << fixed << setprecision(2) << B << endl;
}
int main(){
init();
sol();
}