That's One Hanoi-ed Teacher
Time limit2sMemory limit512 MB
Given a legal Tower of Hanoi layout, decide whether it lies on the optimal solution path and if so output the remaining moves to the goal.
- Level
Medium7 of 10
- Topics
- Recursion, Divide and conquer, Implementation
- Solved
- No attempts yet
Problem
Roberta teaches math at a small college, and she has just introduced the Tower of Hanoi to her discrete math class. The puzzle has three pegs and disks with radii . At the start every disk sits on the start peg, ordered by increasing size from top to bottom. The object is to move all of them to the destination peg under two rules:
- You move only one disk at a time.
- At no point may a larger disk lie on top of a smaller disk.
The optimal solution for disks takes moves, so it passes through exactly configurations, counting the start and the goal. The picture below shows the optimal solution for , with the start peg on the left and the destination peg on the right.

While the students work, Roberta wants to look at a layout and decide whether it is one of those configurations. If it is, she also wants to tell the student how many moves are left to the goal, which is every disk stacked on the destination peg in decreasing size from bottom to top. Write the program she asks for.
Input
Input consists of three lines, each line representing one peg. Each line starts with a non-negative integer , the number of disks on that peg, followed by integers listing those disks from the bottom of the peg upward. The first line is the start peg and the third line is the destination peg. Disk numbers are the consecutive integers to , where the number is the radius of the disk, and . The given layout is a legal configuration of the puzzle: on every peg the radii strictly decrease from bottom to top.
Output
Print No if the given configuration is not in the optimal solution sequence. Otherwise print the minimum number of moves still required to reach the goal configuration.