Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-05-22Google Code Jam 2011 Round 1A

Google Code Jam 2011 Round 1A A FreeCell Statistics

| 23:13 | Google Code Jam 2011 Round 1A A FreeCell Statistics - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 1A A FreeCell Statistics - SRM diary(Sigmar) Google Code Jam 2011 Round 1A A FreeCell Statistics - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

サンプルが親切。

PGが0か100のときに、PD!=PGだと矛盾するのでBroken

それ以外の場合は、PGはGの上限がないので任意の値で実現可能

(典型的にはGを100の倍数とすると、G*(PG/100)が必ず整数になるので、G*(PG/100)がN以上となるようにGを適当な100の倍数とすれば必ず実現できることが分かる)

ということで後はN以下のDでD*(PD/100)が整数となるものがあればPossibleということになる

式を変形するとD*(PD/100)=x⇔PD/100=x/D

すなわちPD/100を約分すると最小のDはその分母となる

ユークリッドの互除法を使用して最小のDを求め、N以下となるかどうかを確認すればOK

small通った

Largeダウンロード、一瞬で回答出た

中身を確認すると全てBrokenになっている・・・

問題文の上限を見直すと、10^15と書いてある。オーバーフローしている。不注意だった。

intをlong longに直す。

再度run。今度はPossibleがたくさん出てきたので良さそう

提出

ここまで15分くらい


ソースコード

main関数は省略

solve関数がfalseのときBrokenを出力、trueのときPossibleを出力します

ll gcd(ll a, ll b) {
	while(b) {
		a=a%b;
		swap(a, b);
	}
	return a;
}

bool solve(ll N, ll Pd, ll Pg) {
	if(Pd<100 && Pg==100) return false;
	if(Pd>0 && Pg==0) return false;
	if(Pd==0 || Pd==100) return true;
	ll m=100;
	ll g=gcd(m, Pd);
	if(m/g>N) return false;
	else return true;
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110522