3543 iChess

問題概要

白と黒の正方形のタイルがw,b枚ずつある。
このタイルを使って市松模様の正方形を作りたい。作れる最大の正方形の一辺の長さを求めよ。そのような正方形が作れない場合はImpossibleを出力せよ。


0≦w,b≦10000とする。

解法

正方形のサイズは141*141以下なので、141通り作れるか試してみる。


市松模様を作るので、一辺をsとすれば、片方の色が(s*s+1)/2枚、もう一色がs*s/2枚必要になる(切り捨て)。
多いほうに多く使うほうの色を割り当ててよい。

ソースコード

int main(){
	int w,b;
	scanf("%d%d",&w,&b); if(w<b)swap(w,b);
	for(int s=150;s>0;s--)
	{
		int x=(s*s+1)/2,y=s*s/2;
		if(w>=x&&b>=y){
			printf("%d\n",s); goto END;
		}
	}
	puts("Impossible"); END:;
	
	return 0;
}