MBEEWALK - Bee Walk


A bee larva living in a hexagonal cell of a large honey comb decides to creep 
for a walk. In each “step” the larva may move into any of the six adjacent cells
and after n steps, it is to end up in its original cell.
Your program has to compute, for a given n, the number of different such larva walks.
Image and video hosting by TinyPic

Input

The first line contains an integer giving the number of test cases to follow. 
Each case consists of one line containing an integer n, where 1 ≤ n ≤ 14.

SAMPLE INPUT
2
2
4

Output

 
For each test case, output one line containing the number of walks. Under the
assumption 1 ≤ n ≤ 14, the answer will be less than 2^31.

SAMPLE OUTPUT
6
90

hide comments
amulyagaur: 2018-03-12 03:58:50

why #greedy??

learner4life: 2017-09-09 03:22:43

Instead of using maps for negative coordinates, it is better to offset the origin by some amount. Then an array can be used.

mahilewets: 2017-08-31 09:05:27

Really
It is just a 2d coordinate system with THREE parameters

lord_poseidon: 2017-07-23 20:16:27

Understand hexagonal coordinate system, game is over

Nafis Islam: 2017-06-08 03:17:19

simple dp :D

ashishranjan28: 2016-11-04 11:06:19

Last edit: 2017-05-25 08:31:37
xxbloodysantaxx: 2015-07-11 15:28:21

I hard coded the value but I cannot understand how to memoize it ! When using Maps , the container is always empty initially ! Which is one of the values which leads to TLE as it was taking 2 seconds for n=14 !

Got it used another map for marking that a state was visited or not :D

Last edit: 2015-07-11 15:41:07
Deepak Singh Tomar: 2015-07-07 14:50:40

for those who are stuck at how to store intermediate results for -ve coordinates... use map... :)

AlphaDecay: 2015-06-08 23:38:15

Awesome !! :D

Dipankar Jana: 2015-04-22 07:59:33

problem is not displaying.


Added by:~!(*(@*!@^&
Date:2009-02-24
Time limit:0.133s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE