UVa 10918

From Algorithmist
Jump to: navigation, search

Contents

[edit] 10918 - Tri Tiling

Tri Tiling

[edit] Summary

Determine in how many ways can a 3xN rectangle be completely tiled with 2x1 dominoes.

[edit] Explanation

It's a typical problem on dynamic programming. One possible solution is described below.

Let f(n) be the number of tilings of a 3xN rectangle (which is what we're looking for) and let g(n) denote the number of tilings of a 3xN rectangle with one of its corner squares removed.

These functions satisfy the recurrent relations: f(n) = f(n - 2) + 2g(n - 1),g(n) = f(n - 1) + g(n - 2). The formulas can be illustrated as follows:

********   AA*******   AA******   A*******
******** = BB******* + B******* + A*******
********   CC*******   B*******   BB******
  f(n)   =  f(n-2)   +  g(n-1)  +  g(n-1)

********   A********   AA*******
******** = A******** + BB*******
 *******    ********    CC******
  g(n)   =   f(n-1)  +   g(n-2)

The boundary values for the relations are: f(0) = 1,f(1) = 0,g(0) = 0,g(1) = 1.

For any odd value of N, the number of tilings of a 3xN rectangle is 0.

[edit] Input

0
1
2
8
12
30
-1

[edit] Output

1
0
3
153
2131
299303201
Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox