UVa 10152
From Algorithmist
Contents |
[edit] 10152 - ShellSort
[edit] Summary
Help King Yertle build his turtle throne by figuring out an optimal strategy for moving the turtles. A turtle moves by crawling out of its place in the turtle stack and climbing to the top.
[edit] Explanation
It seems as though King Yertle has set a tough task for you, but trying a few examples on paper should lead you to the following insights:
- A turtle doesn't have to move if it is already above all the turtles it is supposed to be above. Otherwise, it must move.
- If a turtle moves to the top, then the turtle that is supposed to be directly above it must also move.
- Applying this recursively, this means if turtle x must move, then turtles
must also move, in that order.
So, the problem boils down to finding the lowest (in terms of placement on the wanted order of the stack) turtle that must move, and printing its name and the name of every turtle above it in the wanted ordering of the stack.
[edit] Gotcha's
- Print a blank line after every case.
[edit] Input
2 3 Yertle Duke of Earl Sir Lancelot Duke of Earl Yertle Sir Lancelot 9 Yertle Duke of Earl Sir Lancelot Elizabeth Windsor Michael Eisner Richard M. Nixon Mr. Rogers Ford Perfect Mack Yertle Richard M. Nixon Sir Lancelot Duke of Earl Elizabeth Windsor Michael Eisner Mr. Rogers Ford Perfect Mack
[edit] Output
Duke of Earl Sir Lancelot Richard M. Nixon Yertle
