SPOJ.com - Problem MNTILE

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.

tiling 10 by 10 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:

Information

All outputs will fit on 64-bit signed integer and less than 10¹⁵.

You may try M3TILE, M4TILE, or M5TILE first.

Submit solution!

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

Submit solution!

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.