Google Code Jam 2014 Round 1C : A. Part Elf

GCJ Round1Cを練習。本番出てたらB-smallに時間がかかって抜けられたかどうかわからないな…。
https://code.google.com/codejam/contest/3004486/dashboard#s=p0

問題

40世代前の先祖は100%エルフか100%人間かどちらかである。
子供は、両親の属性を半分ずつ受け継ぐため、エルフの割合は両親の平均値となる。

今、自分の属性におけるエルフの割合が与えられる。
何世代前に100%エルフの先祖かいた可能性があるか、最も近い値を答えよ。

解法

今自分のエルフの割合をp/qとする。

まず、p/qを約分しておく。
前提として子供は両親の属性の平均値となり、かつ40世代前は100%か0%エルフなので、qは2の累乗で(2^40)以下でなければならない。

両親における置いて片方のエルフの割合が最大である場合、片方は2p/q、片方が0%となる。
この推論より、１世代さかのぼると最大でエルフの割合が倍になる。
よってp/qが1を超えるまで２倍にしていけばよい。

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	ll P,Q;
	scanf("%lld/%lld",&P,&Q);
	ll g=__gcd(P,Q);
	P/=g;
	Q/=g;
	
	if(Q&(Q-1)) return _P("Case #%d: impossible\n",_loop);
	FOR(i,41) {
		if(P>=(Q>>i)) return _P("Case #%d: %d\n",_loop,i);
	}
	return _P("Case #%d: impossible\n",_loop);
}

まとめ

これは割とすんなり。