Cocoa... That's Not It
Time limit1.5sMemory limit1024 MB
Given the order in which Cocoa places the odd-numbered books, choose each even-numbered book so it lies strictly between its two neighbors in value.
Problem
Cocoa and Chino were looking for books in the library. Then Cocoa accidentally knocked over a bookshelf that held books.
Luckily, each book has a number from 1 to in order, so it was not hard to figure out the original order of the books on the shelf.
Cocoa and Chino agreed to split up the search. Cocoa found the books with odd numbers, that is, the books numbered . Chino found the books with even numbers, that is, the books numbered .
From now on, starting with Cocoa, they take turns placing the books they found, from the front. Let be the number of the book Cocoa places at the -th position, and the number of the book Chino places at the -th position. For every integer , book is placed in front of book , and book is placed in front of book .
Cocoa does not care much about placing books in order. So after placing a book, she picks any one of the remaining books as the next one to place.
Chino wants at least a minimal order to be kept. He checks the book Cocoa picked and places a book whose number lies between the numbers of the two books Cocoa places on either side of it.
That is, for every integer , either or must hold.
Write a program that tells Chino how to place the books in this way.