Codeforces #499 Div1 A. Fly

なんか割といい順位だった。
http://codeforces.com/contest/1010/problem/A

問題

N個の星を順にたどる。
各星にはパラメータA[i],B[i]がある。
A[i]の星に着陸するとき、重さのA[i]分1の燃料を消費する。
B[i]の星に着陸するとき、重さのB[i]分1の燃料を消費する。

重さMの宇宙船が全部の星を辿って戻るとき、燃料を最低どれだけ積めばよいか。

解法

二分探索でも解けるが、逆にたどる方が安全。
着陸または離陸後の重さがMとなるようにするには、M+x = A[i]*xとなるようなxだけ余分に燃料を積めばよい。

int N;
double M;
int A[1010],B[1010],C[2010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	y=M;
	FOR(i,N) {
		cin>>x;
		C[(N-1-i)*2+1]=x;
	}
	FOR(i,N) {
		cin>>x;
		if(i==0) C[0]=x;
		else C[(N-1-i)*2+2]=x;
	}
	
	FOR(i,2*N) {
		if(C[i]==1) return _P("-1\n");
		M=M+M/(C[i]-1.0);
	}
	_P("%.12lf\n",M-y);
	
}

まとめ

二分探索危ないなと思って避けたけど、二分探索でも一応通るようだ。