Problem F
That's One Hanoi-ed Teacher
Roberta Roberts (the older sister of Bobby in Problem F)
teaches math at a small college, and has just introduced the
Tower of Hanoi to the students in her Discrete Math class. In
case you’ve been in a Tibetan monastery for the past several
years and have never heard of the Tower of Hanoi puzzle
(doubtful for several reasons), here’s a brief description. The
puzzle consists of three pegs, and
-
You can move only one disk at a time
-
At no point may a larger disk lie on top of a smaller disk
It’s well known that the optimal (i.e., shortest) solution
for a Tower of Hanoi puzzle with
![\includegraphics[width=0.75\textwidth ]{hanoi2}](/problems/thathanoi/file/statement/en/img-0001.png)
As part of an in-class lab, Roberta will hand out Tower of
Hanoi sets to her students and let them try to solve the
problem on their own. As she goes around the room, she realizes
that for the larger size sets, she has trouble looking at a
current layout of the disks and determining whether the student
is on the right track or not. In other words, she wishes to
know whether or not a given configuration of the puzzle is one
of the
Input
Input consists of three lines, each line representing one
peg of a Tower of Hanoi configuration. Each of these lines
starts with a non-negative integer
Output
Display No if the given configuration is not in the optimal solution sequence; otherwise display the minimum number of remaining moves required to get to the final configuration. Note that the given configuration might violate the rules of the puzzle (i.e., have a larger disk on top of a smaller disk), in which case you should output No as well.
Sample Input 1 | Sample Output 1 |
---|---|
1 3 2 2 1 0 |
4 |
Sample Input 2 | Sample Output 2 |
---|---|
1 3 0 2 2 1 |
No |