Editorial for COCI '20 Contest 3 #1 Knjige


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

This task has many solutions, and we will describe one of them.

Notice that if we can get all books to be on the right shelf, sorted from thickest to thinnest (in the order from top to bottom), then we can just move them one by one back to the left shelf.

We can accomplish that by repeating the following algorithm as long as the left shelf is not empty:

  • Use the left hand to move books from the left shelf to the right shelf until we get the thinnest book from the left shelf to be on top.
  • Take the top book from the left shelf in the right hand.
  • Return all books that were moved in the first step back to the left shelf using the left hand.
  • Put the book from the right hand on the right shelf.

Comments

There are no comments at the moment.