10359 - Tiling

[ditrix]

Can anyone tell me why the right answer for input "0" is "1" and not "0"?
Does it mean, that exists exactly one way to tile nothing by anything?
And if the answer is positf, what is this way?

[kmhasan]

The answer for 0 is 1. There is exactly one way to tile a 2x0 board -- that is to tile it with 0 tiles. The reasoning is analogous to choosing 0 items from n items. I hope you'd agree that it's valid.

[bsd_lover]

I am compeletly stumped. Can't figure out the recurrence relation. Any hints anyone ?

[mf]

Here's the solution:
f(0) = 1
f(1) = 1
f(n) = f(n - 1) + 2 * f(n - 2)

The recurrence follows from the fact that in general 2xn rectangle there are just three possible tiling schemes:
1. Use a vertical 2x1 piece, and recursively tile the remaining 2x(n-1) rectangle.
2. Use a 2x2 piece and tile 2x(n-2) rectangle.
3. Use two horizontal 1x2 pieces and tile 2x(n-2) rectangle.

Graphically they look like (`#' and `*' stand for pieces, dots - the remaining part of the rectangle):

Code: Select all

#....    ##...    ##...
#....    ##...    **...
  1        2        3

[bsd_lover]

Thanks mf , I actually figured it out before that after I googled for it Its a nice problem. But quite easy once the relation is found. Mind you , you also need a BigInt library handy.

[Ashganek]

Could anyone take a look and tell me why I got CE? (it works on my computer)

// cut...

[Solaris]

I have found at least two lines where u can get CE

Code: Select all

1. c->len = max(a->len, b->len)+1;                      //'max' : undeclared identifier
2. if(  n == 1 or n == 0 ) { return int_to_bint(1); }  //'or' : undeclared identifier

And by the way, I dont know about any C/C++ compiler where u can pass the latter case. Which compiler did u use ?

[Ashganek]

dev-cpp.

since when or is undeclered ?

which header i have to include to get max in gcc then?

[Ashganek]

Ok, I defined my own max and switched to cstdio and I got it

[sunny]

i cant understand why the relation isnt this:
f(n)=f(n-1)+f(2)*f(n-2)
or, f(n)=f(n-1)+3*f(n-2)

isn't there another way to use two vertical 1x2 pieces
& tile 2*(n-2) rectangle.

[mf]

In the derivation I've posted above, the case with two vertical pieces is included in the case #1.

Draw all the tiling of 2x3 rectangle by hand. It will help you understand the problem better.

[rossi kamal]

mf


i got ac with DP..
With recursion i m stuck at bigger inputs
I have used the big integer libraray...


May you tell some more recurrence of 2*1
2*2 0r 2*3 dominoes in 2*n or 3*n 0r n*n
rectangle

wish to learn about them...


Thanks in advance



Rossi

[Angeh]

Another Easy recursion is

for f(n=even) 2*f(n-1)+1
for f(n=odd) 2*f(n-1)-1

convince yourself ........