M3TILE - LATGACH3


In how many ways can you tile a 3xn rectangle with 2x1 dominoes?

Here is a sample tiling of a 3x12 rectangle.

Input consists of several test cases followed by a line containing -1.
Each test case is a line containing an integer 0 ≤ n ≤ 30. For each test
case, output one integer number giving the number of possible tilings. 

SAMPLE INPUT

2
8
12
-1

SAMPLE OUTPUT

3
153
2131

hide comments
ushould_study: 2018-09-13 13:56:18

my first dp, emotional moment for me :D lol ac in one go YAY !

karan_yadav: 2018-07-08 13:09:48

Heckuva question!!!
After this question, try (https://www.spoj.com/problems/GNY07H/).

P.S. - Hint: Try making equations for different cases.

Last edit: 2018-08-05 13:44:12
julkas: 2018-07-08 12:06:34

Great problem.

dsingh_24: 2017-08-14 15:40:38

recursive dp :)

kass_97: 2017-01-12 21:26:01

Dp does it all

lt: 2016-11-21 19:07:26

Simple recursion gets AC in 0.00.

Last edit: 2016-11-21 19:07:46
gustavoaca1997: 2016-11-09 05:07:56

beautiful problem

kushalanand: 2016-11-02 15:21:24

n=0 ,ans =1. 1 WA.

mahmood_2000: 2016-08-28 00:28:35

I got TLE so I made the array size smaller and got AC...crazy world!!!

vignesh97: 2016-06-08 10:09:46

Good problem. AC in first go :p


Added by:~!(*(@*!@^&
Date:2009-02-17
Time limit:0.600s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM