## MNTILE - Tiling a WxH Grid With Dominoes

no tags

Write a program that takes as input the width, W and height H of the grid and outputs the number of different ways to tile a W-by-H grid with (2x1) dominoes.

Score is the length of your source.

### Input

The first line is an integer T(1 ≤ T ≤ 276), denoting the number of test cases. Then, T test cases follow.

For each test case, there are two integers W and H(0 ≤ W+H ≤ 22) written in one line, separated by space.

### Output

For each test case, output the number of different ways to tile a W-by-H grid with (2x1) dominoes.

### Example

```Input:
6```
`1 2`
`2 3`
`3 4`
`4 5`
`5 6`
```6 7

Output:```
```1
```
`3`
`11`
`95`
`1183`
`31529`

### Information

All outputs will fit on 64-bit signed integer and less than 1015.

You may try M3TILE, M4TILE, or M5TILE first.

hide comments
 < Previous 1 2 Next > Aditya Pande: 2013-12-15 13:56:31 Thnx finally got AC and i learnt a lot is there any other way to use the c pi except acos(-1) Last edit: 2012-07-08 04:09:59 Aditya Pande: 2013-12-15 13:56:31 how to have the long long as well as the fractional computation Ans: You can round it again into integer and save it on long long int variable... and for fractional computation it will not overflow until 10^15. I have tested it ;) edit: thnx edit: why m i getting WA in submission id 7272946 or 7272952 Ans: Check when W and H are odd number. Last edit: 2012-07-07 07:42:47 15972125841321: 2013-12-15 13:56:31 @Tjandra can u plz tell why m i getting w.a... my sub id 7266788 thnks Ans: Your program overflow for this test case: 1 10 4 your ans: 18060 correct ans: 18061 and some other test cases... thnks ... must be the differnce in predefined values of pi in c and python.. Ans: Yes but, there is 1 AC python solution... Last edit: 2012-07-07 19:24:56 Francky: 2013-12-15 13:56:31 Edit : silly mistake ! Last edit: 2012-07-04 15:24:15 Mitch Schwartz: 2013-12-15 13:56:31 Are you sure test data is correct? I've examined my output for all possible inputs. Ans: Sorry, that was my silly mistake... I had uploaded input file for output file, and output file for input file... Test data corrected... Thanks :) Last edit: 2012-07-03 03:01:09

 Added by: Tjandra Satria Gunawan Date: 2012-07-02 Time limit: 1s Source limit: 300B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET Resource: Generalization of M3TILE, M4TILE/GNY07H, and M5TILE problems.