KUPC2014 : E - 何しちゃおっかな？

1WAしたけどなんとか自力正答。
http://kupc2014.contest.atcoder.jp/tasks/kupc2014_e

問題

NxMの正方形を、J型とL型の４マス分の連結ブロックを最低１個以上使って埋めたい。
埋めることは可能か答えよ。

解法

問題文の例を見てわかるとおり、J型またはL型を２つ合わせると2x4の長方形ができる。
よって、NとMの片方が４の倍数でもう片方が２の倍数で、かつJとL両方1回以上使うためにN*Mが16以上なら敷き詰められる。

…ここまではわかりやすいが、実はもう一つ以下の形状がある。

ABBBCCCD
ABDDDECD
AADEEEDD

上記3x8の形状を使うと、NとMの片方が８の倍数で、もう片方が３以上なら敷き詰められることがわかる。

void solve() {
	int f,i,j,k,l,x,y;
	cin>>i;
	while(i--) {
		cin>>x>>y;
		
		if(x%2==0 && y%2==0 && (x%4==0 || y%4==0) && 1LL*x*y>=16) cout << "Possible" << endl;
		else if((x%8==0 || y%8==0) && x>=3 && y>=3) cout << "Possible" << endl;
		else cout << "Impossible" << endl;
	}
}

まとめ

1WAしたが、その後はすぐ3x8が思いつけた。