10644 - Floor Tiles

pingus · Post by **pingus** » Wed May 05, 2004 1:16 pm

What is the output for

1 10 1 10

Per · Post by **Per** » Wed May 05, 2004 3:20 pm

The output is 38.

pingus · Post by **pingus** » Wed May 05, 2004 4:51 pm

Hello

Thank you for the outputs Per. My code is wrong !

I was thinking that build with that title is equivalent to build with 2*3 titles if we search a rectangle ?

Per · Post by **Per** » Wed May 05, 2004 4:59 pm

No.. for instance, a 9x5-rectangle is possible, but you can't build it out of 2x3-tiles.

pingus · Post by **pingus** » Wed May 05, 2004 7:58 pm

Ok. I get it! (Thank to you)

A 5x9 was crucial to find a Mathematical Solution !!
I build it with two "basic" titles.

Now, There is possible other different solution ?

ranjit · Post by **ranjit** » Thu May 06, 2004 12:19 pm

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.

technobug · Post by **technobug** » Thu May 06, 2004 3:29 pm

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...

little joey · Post by **little joey** » Thu May 06, 2004 4:47 pm

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...

Try to combine smaller rectangles into bigger ones.
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 non-primes...

bugzpodder · Post by **bugzpodder** » Thu May 06, 2004 5:56 pm

Per wrote:No.. for instance, a 9x5-rectangle is possible, but you can't build it out of 2x3-tiles.

This is the key insight.

DJY · Post by **DJY** » Fri May 07, 2004 1:28 am

I have a question.

How to know how many kinds of "basic rectangle" are and how to find them.

sumankar · Post by **sumankar** » Fri May 07, 2004 6:30 am

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.

Code: Select all

http://www.stetson.edu/~efriedma/order/index.html

Let me know if I am wrong.

Suman

dll · Post by **dll** » Mon May 10, 2004 6:31 pm

anyone tell me what's the output for input

4
1 100 1 100
100 1 100 1
100 100 100 100
1 1000 1 1000

thanks in advance

Dreamer#1 · Post by **Dreamer#1** » Fri May 14, 2004 3:32 am

Someone please help. I'm getting WA in this problem.

For the input:

Code: Select all

4 
1 100 1 100 
100 1 100 1 
100 100 100 100 
1 1000 1 1000

My solution gives output:

Code: Select all

Anyone with AC please give the correct output.

Thanks a lot.

-Dreamer

tep · Post by **tep** » Fri May 14, 2004 5:14 am

little joey wrote:It looks somewhat like a 2 dimensional prime sieve, but now we're after the non-primes...

can you give more hint?

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

ranjit · Post by **ranjit** » Fri May 14, 2004 7:56 am

My ac code gives the op :

Code: Select all

hope this helps.

ranjit.

OJ Board

10644 - Floor Tiles

10644 - Floor Tiles

hi everyone

Some hints