UVa 10644

From Algorithmist
Jump to navigation Jump to search

10644 - Floor Tiles[edit]

Summary[edit]

This problem is designed to be one of those "write-code-that-you-don't-really-need" problem.

Explanation[edit]

Follow the instructions, write brute force code that will time out (this code is what you don't really need in your submission). Find a pattern. Trivialize the problem. Write a solution that takes 20 lines (if you want to place high on the rank list, then you need to do a little bit more thinking and some DP).

A kitchen is tilable if its area is divisible by 3. The 5x9 kitchen is tileable. Also, using the facts that 2x3 blocks are tileable, you can build up larger rectangles from those base blocks. Hence convince yourself that if the kitchen is large enough and its area is divisible by 3, then it can be tiled.

Gotcha's[edit]

  • L2 can be smaller than L1.
  • W2 can be smaller than W1.

Input[edit]

7
2 2 2 3
2 3 3 4
3 3 3 3
2 2 2 4
1 6 1 6
1 1 1 1
1 10 1 10

Output[edit]

1
2
0
1
13
0
38