How to solve the Tower of Hanoi problem?

Question

Algorithms

Link to the problem https://acm.timus.ru/problem.aspx?space=1&num=1054

I tried to implement the "optimal algorithm", which is specified in the problem in two ways:

1. We create three arrays (or stacks), with the Tower of Hanoi in the first array. Then hanoi(N, From, To, Temp)flips the top element from from to to. After running the algorithm, it turns out that at the end on a disk with a width of 1 there are disks with a width of 5,4,3,2. That is, 1-5-4-3-2, which contradicts the conditions of the problem
   
2. We do not create any arrays, we just do what is indicated in the optimal algorithm. At the same time, it is not clear how it is implemented Writeln(N, From, To);- if this is just the output of three values, then it is not clear what role they play - I do not get transferred from the first rod to the second tower of Hanoi.
   

   1 1 2
   2 1 3
   1 2 3
   3 1 2
   1 3 1
   2 3 2
   1 1 1

I think the main problem is not understanding the optimal algorithm that is provided in the problem. What is he doing? Optimal transfer of the Tower of Hanoi from the first rod to the second? If so, is it enough to simulate this algorithm and see if the desired combination is obtained or not? And output the number of steps if yes, -1 if not.

Answer 1

Writeln(N, From, To);says "move disc N from the pole from to the pole to". At the same time, it is guaranteed by construction that the disk N lies on the top of from, and something more or nothing lies on to.
The algorithm really optimally transfers disks from a given pole to a given one.
You can just simulate it, of course, but it will be slow. The algorithm has 2^N-1 steps. For N up to 31, this is 2 billion steps and is unlikely to fit in 1 second. But you can think a little and solve the problem in just N steps.
Hint: look where you have the biggest disk in the input sequence? In the algorithm, the first half of the action lies on the initial pole, and the second half - on the final pole. He is never average. You can already immediately understand in which half of the 2^N positions the given configuration should lie.