greentree888's blog

By greentree888, history, 2 weeks ago, In English

In this problem, what if we are given a rectangle of side a*b instead of a square (a*a)?

In other words, how many minimum rectangles with sides a*b would be required to cover the surface of a rectangle n*m?

(Note: We can rotate the rectangles by 90°)

Thanks a lot in advance.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

This is similar to counting tiles in CSES do check it out.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nope, counting tiles in CSES fixes the sizes at 1x2 and asks how many ways to fill, not the minimum number of tiles needed to fill.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Somewhat similar but in this case smaller rectangles are allowed to cross the boundaries of the bigger rectangle.

    Also here we need to count total number of rectangles needed instead of total possible ways.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we rotate the rectangles by an angle not divisible by $$$90^\circ$$$?

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by greentree888 (previous revision, new revision, compare).

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The only helpful?? idea that occured to me is:

Only right and bottom sides can be run over in an optimal solution.