Consider the classic Towers of Hanoi problem, where there are ~N~ disks are on peg A and they need to be moved to peg C, with peg B as an intermediate place to store disks.
There are six possible moves that can be made - we denote
xy as a move of the top disk from peg
y. The six moves are therefore
Assign each move a unique priority.
The claim is that one can blindly apply the following algorithm to solve the Towers of Hanoi problem:
while the problem is not yet solved: find the highest priority move that can be executed, such that a disk is not moved twice in two consecutive moves execute that move
Determine if it is possible to solve the Towers of Hanoi problem given the priorities present, and if so, count how many moves are executed in order to solve the problem. The disks may end up on peg B.
~1 \le N \le 30~
The first line contains a single positive integer, ~N~.
The second and last line contains a permutation of the six moves. The first move has the highest priority and the last move has the lowest priority.
If it is impossible to solve the problem in finite time following the above algorithm, output
Otherwise, output the number of moves needed.
3 AB BC CA BA CB AC