UVa 10152

From Algorithmist
Jump to navigation Jump to search

10152 - ShellSort[edit]

Summary[edit]

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.

Explanation[edit]

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 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.

Gotcha's[edit]

  • Print a blank line after every case.

Input[edit]

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

Output[edit]

Duke of Earl

Sir Lancelot
Richard M. Nixon
Yertle