Google Code Jam 2014 Qualification Round : A. Magic Trick、B. Cookie Clicker Alpha

今年もGCJが開始。
無事満点スタートで幸先が良いね。
https://code.google.com/codejam/contest/2974486/dashboard#s=p0
https://code.google.com/codejam/contest/2974486/dashboard#s=p1

A. Magic Trick

1～16のカードを4x4に並べる、ということを２回行う。
回答者は事前に１枚カードを定め、２回カードを並べた際選んだカードが何列目にあるかを返す。
回答者の回答をもとにカードを１枚に絞れるならその番号を返せ。
カードが２枚以上までしか絞れない場合や、１枚も対象カードがない場合、その旨を返せ。

両方の回答に含まれるカードが何枚あるかbitmaskでカウントした。

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	int mask1=0,mask2=0;
	cin>>x;
	FOR(i,16) {
		cin>>j;
		if(i/4==x-1) mask1 |= 1<<j;
	}
	cin>>x;
	FOR(i,16) {
		cin>>j;
		if(i/4==x-1) mask2 |= 1<<j;
	}
	
	x=mask1&mask2;
	if(__builtin_popcount(x)==0) _P("Case #%d: Volunteer cheated!\n",_loop);
	else if(__builtin_popcount(x)>1) _P("Case #%d: Bad magician!\n",_loop);
	else {
		FOR(i,16) if(x&(1<<(i+1))) _P("Case #%d: %d\n",_loop,i+1);
	}
}

B. Cookie Clicker Alpha

WebゲームCookie Clickerを題材にした問題。

初期状態でクッキーは0枚であり、秒間２枚のペースで焼きあがる。
ここでクッキー所持数がC枚を超えた場合、C枚を消費してクッキー工場を購入可能である。
クッキー工場を１個買うごとにクッキー生成ペースがF枚/秒上昇する。
クッキー所持枚数がX枚に到達する最短時間を求めよ。

クッキー工場を買う場合、C枚になった時点で買うのが良い。
よってクッキー工場をp回買う場合、かかる時間は

である。
後はpを0～100000位で総当たりして時間が最小になるpを求めればよい。

double C,F,X;
void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>C>>F>>X;
	double mi=X/2.0;
	double S=0;
	FOR(i,100501) {
		mi=min(mi,S+X/(2+i*F));
		S+=C/(2+i*F);
	}
	
	_P("Case #%d: %.12lf\n",_loop,mi);
}

まとめ

このあたりはまだ簡単。