RANJAN02 - Tower Of Hanoi - Revisited

no tags 

Given 3 three pegs: leftmost peg A, middle peg B and rightmost peg C.Find the shortest sequence of moves that transfers a tower of n disks from the left peg A to the right peg C, if direct moves between A and C are disallowed. (Each move must be to or from the middle peg B.)

Constraints:
1. Initially the left peg A in stacked by n disks in the order of decreasing size.
2. Only one move cand be done at a time and never moving a larger one onto a smaller.
3. Number of moves will always be less than 2^64.
4. 1 <= n <= 35

Input

Input begins with a integer t, followed by t lines. Each line has the no. of pegs n.

Output

For each test case, output the minimum no. of move required to transfer the n disks from peg A to peg C.

Example

Input:
4
1
2
5
10

Output:
2
8
242
59048

hide comments
up79: 2017-06-28 14:00:57

AC in one go :)

vengatesh15: 2017-03-27 15:36:23

easy dp AC with little precomputation and O(1)

kass_97: 2017-01-01 12:56:10

Easy....AC at once

vikikkdi: 2016-07-06 18:07:55

little precomputation with dp and then o(1) retriveal.
why using powers @akshayvenkat

Last edit: 2016-07-06 18:08:21
mkfeuhrer: 2016-06-24 22:02:21

python rocks!! 1 line :-)

ranjanakash166: 2016-06-06 10:18:39

check the constraints carefully!!!!!
easy DP...YEEEEEEE

glexey: 2015-12-26 09:22:11

5 lines in python is an overkill. 1 is enough, 2 is plenty for readability.

jarvis: 2015-09-22 19:43:11

5 lines in python !
c++ -> be aware of 35 :) costed 2 WA

:D: 2013-01-23 16:08:29

It's seems to be a subcase of problem VIENTIAN.

abhiranjan: 2013-01-23 16:08:29

@~ - Constraint 3 may help you.


Added by:abhiranjan
Date:2010-09-28
Time limit:0.571s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:IIITM Local Contest