Codeforces #370 Div2 C. Memory and De-Evolution

今回は不参加。出たらCで詰まってそう…。
http://codeforces.com/contest/712/problem/C

問題

１辺Xの正三角形がある。
この正三角形に対し、１回の処理で１つの辺の長さを整数分だけ短くすることができる。
ただし、処理後の３辺は面積が正の三角形をなしていなければならない。

１辺Xの正三角形から１辺Yの正三角形を作るには、上記処理を最少何回行わなければならないか。

解法

X→Yにすると考えると難しい。
逆にY→Xにすることを考えよう。

今３辺の長さが昇順でA,B,Cとする。
この場合、Aをmin(B+C-1,X)に置き換えて行き、全部がXになるまでの回数を求めればよい。

int X,Y;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y;
	int A[3]={Y,Y,Y};
	
	int ret=0;
	while(A[0]<X) {
		x=A[0];
		A[0]=A[1];
		A[1]=A[2];
		A[2]=min(X,A[0]+A[1]-1);
		ret++;
	}
	cout<<ret<<endl;
	
}

まとめ

シンプルな問題ながら面白かったです。