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; }