10644 - Floor Tiles

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10644 - Floor Tiles

Post by pingus »

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

Post by Per »

The output is 38.

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

Post by pingus »

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

Post by Per »

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

Post by pingus »

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

Post by ranjit »

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:

Post by technobug »

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

Post by little joey »

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

Post by bugzpodder »

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

Post by DJY »

I have a question. :oops:
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

Post by sumankar »

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. :roll:
Suman

dll
New poster
Posts: 16
Joined: Fri Oct 17, 2003 9:51 am

Post by dll »

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
Nothing is impossible

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

Post by Dreamer#1 »

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

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:

Post by tep »

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
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

Post by ranjit »

My ac code gives the op :

Code: Select all

5348
5348
0
553448
hope this helps.

ranjit.

Post Reply

Return to “Volume 106 (10600-10699)”