PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: irmuun
Tester & Editorialist: iceknight1093
DIFFICULTY:
1182
PREREQUISITES:
None
PROBLEM:
Is it possible to tile a rectangular floor with length L and width W, using only rectangles whose perimeter isn’t divisible by 4?
EXPLANATION:
Recall that the perimeter of a rectangle whose side lengths are a and b, is 2\cdot (a + b).
For this to be not divisible by 4, we’d need (a+b) to be odd — which means exactly one of a and b must be even, and the other must be odd.
In particular, this means the area of such a rectangle (which equals a\cdot b) must be even.
Now, let A = L\cdot W be the total area of the floor.
Suppose we tile it with k rectangles, and their areas are A_1, A_2, \ldots, A_k.
Of course, since it’s a tiling, A = A_1 + A_2 + \ldots + A_k must hold.
For the tiling to be valid, we need each A_i to be even, as discussed earlier.
Notice that this forces A to also be even, as the sum of some even numbers.
So, if the area A = L\cdot W is odd, the answer is immediately No.
On the other hand, if A is even, the answer is always Yes!
This is because a rectangle with even area can always be tiled using 1\times 2 (or 2\times 1) tiles, which have perimeter 6 and so are usable.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
w, l = map(int, input().split())
print('Yes' if (w*l)%2 == 0 else 'No')