Billy's Books

For this exercise, you’ll be working with the following scenario.

Everyday Billy places a book on his floor, with each book being stacked on top of the previous book. On every third day, in addition to stacking a book to the top, Billy also places another book on top of his bookstack (after placing the new book). If there are an odd number of books, then Billy will move the book in the middle of his bookstack to the top. If there an even number of books, then Billy will take the book at the bottom of his bookstack, and move that to the top. He continues this for all n books.

Write a program billys_books.c which scans two lines of input:

1. A single integer n, which corresponds to the number of books Billy has.
2. A sequence of exactly n characters which corresponds to the order of Billy's final bookstack from bottom to top.

Your program should then output the order in which Billy placed his books.

For example, if billy had placed 11 books in the order ABCDEFGHIJK, then the bookstack would look like this

• Day 1: A
• Day 2: AB
• Day 3: ACB (middle book moved to he top)
• Day 4: ACBD
• Day 5: ACDBE
• Day 6: CBDEFA (bottom book moved to the top)
• Day 7: CBDEFAG
• Day 8: CBDEFAGH
• Day 9: CBDEAGHIF (middle book moved to the top)
• Day 10: CBDEAGHIFJ
• Day 11: CBDEAGHIFJK

Hence, given 11\nCBDEAGHIFJK as input, it should correspond to the order in which Billy placed his books: ABCDEFGHIJK.

The output from your program should look exactly like this:

$ dcc billys_books.c -o billys_books
$ ./billys_books
11
CBDEAGHIFJK
ABCDEFGHIJK

Assumptions/Restrictions/Clarifications

• You may assume the first line of input will be a valid positive integer
• The second line of input will contain exactly n characters, followed by a newline character
• You cannot assume the books are unique (ie. the stack AABBCCDD is valid)
• You cannot assume a particular book can only be moved once (especially for large input size)

CSE Autotest

When you think your program is working, you can use CSE autotest to test your solution.

$ 1511 csesoc-autotest billys_books

Solution

You can view the solution code to this problem here.