"Oook!" said the librarian looking at the new, heavy, steel bookcase in the library. Now he doesn't have to make a tedious trip evrytime someone wants one of the books carefully chain... ehm... placed in the library storage far below. He can now have the most used ones nicely at hand.
Instead of finding out which books are the most used ones he decided for a simpler approach. At the beginning he will simply bring the requested books and put them into the new bookcase. Once the new bookcase is full, every time someone will ask for a book that is not in the bookcase, he will just pick the one that was there for the longest time, take it down to the storage and bring back the new one.
But soon he became lazy and unwilling to make all the journeys downstairs. If only he had a bigger bookcase... he would surely save a few trips to the storage. Or wouldn't he? He ate a banana, scratched his head and started to think.
"Oook?!" growled the librarian finally. After a few dozen bananas he finally found out the sad truth. A larger bookcase won't guarantee him less trips. What's worse, sometimes he could even travel more! And once the Unseen University students find out about this, they will surely start to tease him by requesting books in the right (or, from the librarian's point of view, wrong) order.
Easy: Give an example where the librarian would make more trips with a larger bookcase than with a smaller one. More precisely, find an integer N≥4 and a sequence of book requests such that the number of trips downstairs for a bookcase able to hold N books is strictly smaller than the number of trips for a bookcase of size N+1.
Hard: This time, find a more evil example. Let T(N,S) be the number of trips downstairs the librarian has to make for the sequence of book requests S and a bookcase that can hold N books. Find an integer N≥4 and a sequence of requests S such that:
The first line of the output file should contain two integers N and M, where N (4≤N≤100) is the size of the bookcase and M (0≤M≤300) is the number of book requests.
The second line should contain M space-separated integers b1, ..., bM (1≤bi≤M). Different numbers represent different books, same numbers represent requests of the same book.
An incorrect but correctly formatted output file follows.
Output:3 8 1 8 5 1 5 3 5 4Explanation:
In the beginning the bookcase is empty. For the first three book requests the librarian has to go downstairs to fetch the book. For the fourth and fifth request he does nothing, as the books 1 and 5 are currently in the bookcase.
For the sixth request he has to bring the book 3, and he has to make space for it. Book 1 is the one that is in the bookcase for the longest time, thus the librarian takes the book 1 downstairs and brings book 3 back. At this moment the bookcase holds the books 3, 5, and 8.
For the seventh request he does nothing again, and for the last request he takes book 8 down and brings book 4 up. Together he made 5 trips downstairs.
Credits:
Problemsetter(s): misof
Contest-related materials: YoYo