## 10644 - Floor Tiles

Moderator: Board moderators

pingus
New poster
Posts: 18
Joined: Sat May 03, 2003 10:33 pm

### 10644 - Floor Tiles

What is the output for
1 10 1 10

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
The output is 38.

pingus
New poster
Posts: 18
Joined: Sat May 03, 2003 10:33 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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
No.. for instance, a 9x5-rectangle is possible, but you can't build it out of 2x3-tiles.

pingus
New poster
Posts: 18
Joined: Sat May 03, 2003 10:33 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
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

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

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 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
New poster
Posts: 5
Joined: Sun Oct 12, 2003 9:24 am
I have a question.
How to know how many kinds of "basic rectangle" are and how to find them.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

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

Code: Select all

``````http://www.stetson.edu/~efriedma/order/index.html
``````
Let me know if I am wrong.
Suman

dll
New poster
Posts: 16
Joined: Fri Oct 17, 2003 9:51 am
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

Nothing is impossible

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

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

``````4608
4608
0
468308``````
Anyone with AC please give the correct output.

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.

tep
New poster
Posts: 23
Joined: Fri Jun 13, 2003 6:08 am
Contact:
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 ?

Thanx

regards,
stephanus

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india
My ac code gives the op :

Code: Select all

``````5348
5348
0
553448
``````
hope this helps.

ranjit.