SPOJ.com - Problem M5TILE

M5TILE - The dojo s corridor

no tags

Leo is training his martial arts in byteland's dojo. There is a rectangular (5 × 2n) corridor to join the dojo.

In how many ways W(n) can we exactly cover the corridor with 5n tatamis (2 × 1) ?

Input

There's no input for this task

Output

You should output 17 lines with: W(1), W(2), W(3), ..., W(17)

Example

Output:
8
95
... (15 lines follows)

Score

Score is source length, you have to use less than 190 bytes, the third should be enough.

Information

W(17) fit in a 64bit signed container, W(18) doesn't.

You may try M3TILE or M4TILE first.

After that, you may try those : Tiling a WxH Grid With Dominoes , Corridor I , Corridor II .

Submit solution!

hide comments

< Previous 1 2 Next >

	Dhawal Harkawat: 2015-03-25 14:47:59 ID - 13950139, giving WA, The same code when I run in c++, gives correct output, but I had to code it in Ruby, 'cause Source limit was not passing. I think there is some floating point issues with my ruby code, but I just can't understand it. @problem-setter plzz instruct me, where I am wrong.. (Francky) => Don't use float to check your answers. Last edit: 2015-03-25 15:32:47
	Deepak: 2014-07-06 09:40:31 Why am i getting NZEC..?? --ans(Francky)--> numpy isn't available with spoj server. Last edit: 2014-07-10 01:16:05
	its_time_to_code: 2014-06-20 19:30:34 why my c code giving wrong answer.... --ans(Francky)--> Your last answers are false, due to precision errors with your method. Last edit: 2014-06-20 20:19:31
	Alexandre Henrique Afonso Campos: 2014-02-23 16:20:34 I looked for a formula over the internet. I came out with a new one by substituting variables to short the code. When I was 1 bit to reach Mitch, he decreased his code by two bits.
	Alexandre Henrique Afonso Campos: 2014-01-19 22:08:13 @Rohan Phadke There's a math pattern behind. The technique is search over the internet for articles about tilling, learn the pattern and code that.
	Rohan Phadke: 2013-12-25 21:33:57 what is the technique to solve such problems with such tight source limit constraint? someone pls help!
	Robert Gerbicz: 2013-10-21 18:03:36 Got the first solution in awk.
	John Stephanus Peter: 2013-07-17 05:51:03 How do you make it under 190b for c++??
	Maciej Misiak: 2013-06-21 09:34:58 What is the exact output of this problem? I get WA even if just printing uncompressed numbers on the screen (why length limit is set to the value which disallows printing output generated?). Should endline characters be Unix or Windows? Should there be empty line after output or some other magic like that? --ans(francky)--> Your output format is OK, but you have WA on some values... Good luck. Last edit: 2013-06-21 11:03:55
	Ouditchya Sinha: 2013-05-24 03:02:44 Loved solving this one... any hint on how to go below 100B? :)

Submit solution!

Added by:	Francky
Date:	2012-06-14
Time limit:	1s
Source limit:	190B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	M3TILE extension