kojingharangの日記

A. FreeCell Statistics

18:13 |

• N, PD, PG が与えられる。
• 今日の試合数 <= N、今日の勝率はちょうど PD%、今までの勝率はちょうど PG%。
• 上記のようなことが有りうるかどうかを判定する問題。
• 例えば 10 50 100 なら今日の勝率 50% なのに全体の勝率は 100% にならないのでありえないと答える。

• 今日の試合数 <= N をチェックする。今日の試合数の最小値は、今日の勝率と100の最大公約数で100を割ったものになる。
• 試行錯誤しつつ、今日の勝率>0 なのに全体の勝率=0 とか極端な場合だけチェックすれば全体の勝率についてはなんとでもなるということが判明

• コンテスト終了後、Large incorrect であることが判明。
• Large 通している人のコードで実行した結果と自分のを diff で比べると、N が 10 桁とかでかいときに違っている。
• Large では N <= 10**15 という条件があったのであった！
• int N としていたのを long long N としたら一致。
• くやしけり。
• 提出前にチェックすべき事をリスト化するなど、ミスを減らす仕組みづくりをしないといけない。

（以下、long long に修正後のソース）

int gcd ( int a, int b )
{
	if(a<b)
	{
		int tmp=a;
		a=b; b=tmp;
	}
	
	int c;
	while ( a != 0 ) {
	c = a; a = b%a;  b = c;
	}
	return b;
}

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int ans = 1;
		int pd, pg, d=100, g=100, v;
		ll n;
		cin>>n>>pd>>pg;
		//cout<<n<<pd<<pg;
		v = gcd(d, pd);
		pd/=v; d/=v;
		v = gcd(g, pg);
		pg/=v; g/=v;
		//cout<<pd<<" "<<d<<" "<<pg<<" "<<g<<" "<<endl;
		
		//if(g<d)
		//{
		//	int a=d/g + 1;
		//	g*=a; pg*=a;
		//}
		if((pd!=d&&pg==g)||(pd>0&&pg==0) || d>n)
		{
			cout<<"Case #"<<t+1<<": Broken"<<endl;;
			continue;
		}
		//cout<<pd<<" "<<d<<" "<<pg<<" "<<g<<" "<<endl;
		
		cout<<"Case #"<<t+1<<": Possible"<<endl;;
	}
	return 0;
}

ツイートする