MemSQL start[c]up 2.0 Round 2 : A. Golden System

Round1出てないのでRound2も本番不参加。
http://codeforces.com/contest/458/problem/A

問題

黄金比である数q=(√5+1)/2を考える。このqはq^2=q+1の関係がある。
2つのq進法の数値が与えられるので、大小関係を答えよ。

解法

2つの数値を上の桁から順に比べていき、差が出たらq^2=q+1の関係を用いて、差の分を下の桁に反映していく。

途中の桁で4以上差が出たら、それより下の桁でその差を埋められないため、大小関係がそこで確定する。
また、最後2ケタまで大小が確定しない場合は、最後2ケタxyについてxq+yの正負を計算すればよい。

string A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B;
	FOR(i,110000) s+='0';
	A=s+A;
	B=s+B;
	A=A.substr(A.size()-100005);
	B=B.substr(B.size()-100005);
	FOR(i,100005) A[i]-='0',B[i]-='0';
	FOR(i,100003) {
		int dif=A[i]-B[i];
		if(dif>4) return _P(">\n");
		if(dif<-4) return _P("<\n");
		A[i+1]+=dif;
		A[i+2]+=dif;
	}
	double aa=(sqrt(5)+1)/2*A[100003]+A[100004];
	double bb=(sqrt(5)+1)/2*B[100003]+B[100004];
	if(aa>bb) return _P(">\n");
	if(aa<bb) return _P("<\n");
	_P("=\n");
}

まとめ

なかなか面白い問題だった。