読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #188 Div1. A. Perfect Pair

この回はAを凡ミスでTLE、Bだけ解けて微妙な順位。
http://codeforces.com/contest/317/problem/A

問題

2つの整数ペア(X,Y)と整数Mが与えられる。
ペアの片方の要素をX+Yに置き換える、という処理を繰り返し、ペアのどちらかの要素をM以上にしたい。
必要な処理数を最小化せよ。

解法

X,Yの初期値がM以上なら0回で終了。
それ以外の場合:

  1. X,Yが両方0以下なら値を増やせないのでM以上にできない。
  2. 少なくとも片方が正なら、小さい方をX+Yで置き換える

2番目のステップで、たとえばX<0、Y>0の場合、Xが正になるまでYを足しこむが、1回ずつやってしまうとTLEするので割り算して一気に処理しないといけない。
両方正なら、毎回小さい方が倍以上になるので、数十回やればMを超える。

ll X,Y,M;

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>X>>Y>>M;
	if(X>Y) swap(X,Y);
	if(Y>=M) {
		_P("0\n");
		return;
	}
	
	if(Y<M && Y<=0) {
		_P("-1\n");
		return;
	}
	
	ll ret=0;
	if(X<0) {
		ret += -X/Y;
		X += (-X/Y)*Y;
	}
	while(Y<M) {
		ret++;
		X=X+Y;
		if(X>Y) swap(X,Y);
	}
	cout << ret << endl;
}

まとめ

正負の扱いが独特な問題。

広告を非表示にする