Chris works as the night-shift security guard for a large quiet library in a small city. The library is closed to the public during night houes, and so Chris often finds herself quite bored for long periods of time. When she first started the job she excitedly spent many hours of many long nights reading the multitude of books available, but now years later she has already read and re-read everything of interest.
Preparing to start another long night, Chris gathers some various hardcover books together and brings
them over to a desk by her post. Placing a book down rather carelessly, it teeters on the
edge of the desk for a moment before falling off. After some experimentation, Chris quickly
observes that if a book with length L inches and mass M kilograms is placed with its
edge square with the edge of a desk and then slowly slid off the desk, it will not fall until
the book is overhanging by a distance of L / 2. As the mass is uniformly distributed
throughout the book, this makes sense that once the overhang exceeds L / 2 then the book's
center of mass is no longer on the table.
Chris then takes a second book, this one with a different length L and mass M but similar
width and thickness as the first book. She then stacks it on top of the first book, and sees
how far she can slide each book such that the first book overhangs the table and the second book
overhangs the first book. She then tries to maximize the distance between the end of the top book
in the stack and the edge of the table, which she calls the maximum total overhang.
Some books (in blue and green) overhanging the edge of a black table.
She soon discovers that this maximum total overhang value for two books having lengths L1 and L2 is
less than L1 / 2 + L2 / 2, as extending things this far causes the books to fall off the table.
However the maximum overhang distance is guaranteed to be longer than either individual value
of L1 / 2 or L2 / 2.
Curiously, Chris notices that often she gets a different result once the orders of the two books
are swapped in the stack, with one order able to achieve more maximum total overhang than the other.
She looks over at her stack of 9 books that she was planning to re-read, and quickly gets to
work at this new diversion.
Problem Statement
Given 9 books each with individiual lengths and masses L and M, determine the maximum total
overhang possible when the books are stacked in any order.
All books must remain "square" with the edge of the table. The length measuring L will be
perpendicular with the edge of the table.
Assume books behave as frictionless, perfectly rigid rectangular prisms with uniform density.
Please excuse any "unrealistic" values for book size or mass, for the sake of the problem at hand :)
Input Data
Input data will consists of 9 total lines, each with two values in the format L M
corresponding to the length and mass of a book.
Answer
Should consist of 10 space-separated values - the first value corresponding to the maximum total
overhang achievable by stacking the 9 given books described, followed by the order of those
books in the stack which produces that maximum value, starting with the bottom of the stack. Note
that the list of books given in the input data is 0-indexed.
Error should be less than 1e-6
Example
input data:
1 9
3 2
7 8
6 4
5 5
2 7
4 1
9 3
8 6
answer:
10.765726 0 5 1 4 2 3 8 7 6