KUPC 2014 E - 何しちゃおっかな？

問題

テトリスのL字ブロック

■
■
■■

　■
　■
■■

を両方少なくとも1回ずつ使って、nxmの長方形のフィールドを隙間なく埋めることができるかを判定せよ。
ブロックは回転させてもよいが、反転させたり、重ねたり、フィールドの外に出したりしてはならない。

制約条件

n, mのペアが10000個以下来る。
n, m≦100000

方針

こういうのはマジでムリゲー。

まずnxmが8の倍数じゃないとダメ。（これそんなに自明か？）

2x4は同じブロック2個置くしかなくて、片方が使えないので無理。
2x8からは、2x4を反転してもう一個おけばいいので作れる。

一方が8の倍数のとき、
3x8, 2x8が作れるので、(5以上)x8は全て作れる。
なので1x8だけがダメ。

一方が2の倍数のとき、もう片方は4の倍数なので2x4を敷き詰めればよくて、
でも2x4だけは作れない。それ以外は作れる。

両方が4の倍数のときは2x4を敷き詰めればいいのでできる。

ソースコード

bool ok(int n, int m){
	if((ll)n * m % 8 || n == 1 || m == 1) return 0;
	return !(n == 2 && m == 4) && !(n == 4 && m == 2);
}
int main(){
	int c; cin >> c;
	while(c--){
		int n, m; cin >> n >> m;
		cout << (ok(n, m) ? "Possible" : "Impossible") << endl;
	}
	return 0;
}