HANOICAL - Hanoi Calls

Theory:

  • Towers of Hanoi is an arrangement consisting of three pegs and N discs of radius 1 to N.
  • Each peg can hold zero or more discs, but at any point of time, the radius of the discs must be in decreasing order from bottom to top.
  • A move consists of moving the topmost disc from one peg to another. After the move, the descending order property of pegs must hold.
Traditional problem is: If all discs are stacked up on peg#1, how many moves will it take to move all the discs to peg#2?
Recursive solution: Noting that for disc N to move, from peg #a to peg #b, all discs of size 1 to N-1 must be in peg #c. Hence there is exactly one minimal way to move the discs. After disc N has moved, all pegs from #c must be moved back to #a. If moves(N) denote the number of moves required to transfer N discs between two pegs (both sorted configuration), then moves(N) = moves(N-1) + 1 + moves(N-1); Solving the recurrence yields moves(N) = 2N -1; The idea i am trying to share is that, there is exactly one such move sequence.

Now the problem is that given any initial configuration of the discs, and any final configuration, Can you tell me the minimal number of moves required to change it from initial to final configuration?


Input Format:
The input file consists of multiple testcases.
The first line of each testcase contains one integer, N (1 <= N <= 30)
The second line of each testcase contains N integers, each one of which will be between 1 and 3. The i-th integer tells you the peg number at which disc of radius i is present in the initial configuration.
The third line contains a similar specification for the final configuration.
Input terminates with a line containing a single zero, which must not be processed.

Output Format:
For each testcase print one line containing a single integer, which is the minimal number of moves to make the transfer.

Test data:
100 testcases

Sample Input:
4
1 1 1 1
2 2 2 2
3
1 3 3
2 1 1
5
1 3 2 2 2
2 3 2 1 2
0
Sample Output:
15
6
14
Output Explanation:
TestCase#1:
This is the moves(4) = 2^4 -1;
TestCase#2:
   [peg1, peg2, peg3] = 
#0 [ {1}, {}, {3,2} ]
#1 [ {1}, {2}, {3}  ]
#2 [ {}, {2,1}, {3} ]
#3 [ {3}, {2,1}, {} ]
#4 [ {3}, {2}, {1}  ]
#5 [ {3,2}, {}, {1} ]
#6 [ {3,2}, {1}, {} ]

Added by:Prasanna
Date:2007-10-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp 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 TEXT WHITESPACE
Resource:NITT ACM ICPC Local Contest 2007 [Self/Traditional]

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.