1 10 1 10
10644  Floor Tiles
Moderator: Board moderators
10644  Floor Tiles
What is the output for
hi everyone
hi Per,
how did you find out that 9x5 rectangles are possible.
Only after you mentioned it i started looking how it was possible.
Even then it took me a lot of time.
I would like to know how to find out what rectangles are possible.
how did you find out that 9x5 rectangles are possible.
Only after you mentioned it i started looking how it was possible.
Even then it took me a lot of time.
I would like to know how to find out what rectangles are possible.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Try to combine smaller rectangles into bigger ones.technobug wrote:can anyone point me on how to start looking for the solution? cause i believe i might be looking this problem from the wrong side...
One of the basic rectangles is the 2x3. By putting two of them together, you can form either a 4x3 or a 2x6 rectangle. Continue in this matter and you can form 6x3, 8x3, 10x3, etc., or 2x9, 2x12, 2x15, etc. You can also make other combinations: a 2x6 and a 6x3 (rotated) form a 5x6 (and an 8x6, 11x6, etc.).
Like Per mentioned, 5x9 is also a basic rectangle and can be combined the same way. And there are mixtures (three 2x3 form a 2x9, which can be combined with a 5x9 to form a 7x9).
It looks somewhat like a 2 dimensional prime sieve, but now we're after the nonprimes...

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm
Some hints
Hi,
This is a wonderful problem!
Maybe the following link is a spoiler, but go and study
polyominoes.This is a Triominoes problem if I am not wrong.
Let me know if I am wrong.
Suman
This is a wonderful problem!
Maybe the following link is a spoiler, but go and study
polyominoes.This is a Triominoes problem if I am not wrong.
Code: Select all
http://www.stetson.edu/~efriedma/order/index.html
Suman
Someone please help. I'm getting WA in this problem.
For the input:
My solution gives output:
Anyone with AC please give the correct output.
Thanks a lot.
Dreamer
For the input:
Code: Select all
4
1 100 1 100
100 1 100 1
100 100 100 100
1 1000 1 1000
Code: Select all
4608
4608
0
468308
Thanks a lot.
Dreamer
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.
can you give more hint?little joey wrote:It looks somewhat like a 2 dimensional prime sieve, but now we're after the nonprimes...
1. Is there any mathematical explanation why we can only have 2 building blocks, i.e 2x3 and 5x9?
2. how do you know that mxn rectangle can be built with those building blocks(2x3,3x2,9x5,5x9)?
3. In general, if we have k building blocks, i.e
m1 x n1
m2 x n2
......
mk x nk
how do we determine if pxq rectangle can be built with those k building blocks ?
Tiling is one of my weakness, please help.
Thanx
regards,
stephanus
http://www.harvestsoft.net
Stephanus
Stephanus