Lay 1 * 2 and 1 * 3 tiles on the floor n * m as much as possible

Question

Tiles can rotate.

Example:

Given two tiles 1 * 2 and one tile 1 * 3, and the floor 3 * 3, we put all the tiles on the floor as follows:

AAA ..B CCB 

Now, given n * m floor and p 1 * 2 tiles and q 1 * 3 tiles (the number of tiles is limited). Return the maximum number of tiles that can be laid on the floor. For example, the answer is 3 (you can put 3 tiles on the floor).

Answer 1

Dukelin's answer is wrong. Considering a 5 * 5 floor and 8 1 * 3 tiles. The only way to put all the tiles on the floor:

 AAACD BBBCD EF.CD EFGGG EFHHH 

And this cannot be achieved by replacement.

Then how to do it? I have done a lot of mathematical work and I know well. I will give you some hint:

• Put 1 * 3 tiles first and place 1 * 3 so that we can put 1 * 2 as much as possible (in fact, suppose there are n unclosed floor tiles, so we can put the floor (n / 2) 1 * 2 tiles).
• Be careful with some corner cases. For example, all tiles are 1 * 3, floor 1 * 10, and floor 2 * 10, etc.

If you have any problems, leave me a comment.

Answer 2

There may be some additional difficulties, but here is my idea:

• Fill the entire floor with 1x2 tiles. This should be simple enough, just make sure it consists mainly of parallel tiles, something like this: (black and white - both tiles)

  

  Notice, I just filled the bottom row with horizontal plates, not vertical ones, it's just to fill the grid. And the bottom left tile is empty (you can replace the plate to the right of it with a 1x3 plate).

• If you do not have many 1x2 tiles, fill the grid anyway, they will be deleted in the next step.

• While you do not have enough 1x2 tiles to place, systematically replace 3 parallel 1x2 tiles with 2 1x3 tiles. So:

  becomes

Answer 3

It is unclear what to return. Do you need a set of solutions or just the maximum number? One simple solution can use only 1 * 2 tiles. Obviously, there may be more than 1 * 2 tiles, and then 1 * 3 tiles.

Assumption b=0

 a = n * m div (1*2) 

Assumption a=0 , m>=3 , n>=3

 b = n * m div (1*3)