3543 iChess
http://poj.org/problem?id=3543
概要
黒のタイルと白のタイルが与えられるので、それらを使って作ることのできる
市松模様の正方形の最大サイズを求める。
方針
正方形のサイズ = lに対して
lが偶数 -> w >= l^2/2 && b >= l^2/2が必要
lが奇数 -> min(b,w) >= l*ceil(l/2) + ceil(l/2)
max(b,w) >= l*ceil(l/2) + ceil(l/2) + 1 が必要
なはず・・・
ソース
#include<iostream> using namespace std; int main(){ int b,w; while(cin>>b>>w){ if(b==0&&w==0) { cout<<"Impossible"<<endl; continue; } if(b==0||w==0){ cout<<1<<endl; continue; } int ans = 0; for(int l=1; l<1000; l++) { if(l%2 == 0) { if(w >= (l*l)/2 && b >= (l*l)/2) ans = l; }else{ if(min(b,w) >= l*(l/2) + l/2 && max(b,w) >= l*(l/2) + l/2 + 1) ans = l; } } cout<<ans<<endl; } }