Problem B
Bohemian Bookshelf
When it comes to shelving books, bibliophiles and interior decorators rarely agree: vertical or horizontal—what’s the right way? Ever skeptical of orthodoxy, you embrace both! Your bookshelf displays a composed mix: upright volumes standing with quiet discipline next to a single, neatly arranged stack, like a literary ziggurat. The effect signals bohemian chic with a touch of endearing academic absent-mindedness and just enough polish to suggest you’ve definitely read some of the books.
A book is characterised by its spine height and thickness. It can fit upright if its height does not exceed the bookshelf’s height. Alternatively, books can form a stack by being laid flat on their sides on top of each other; for aesthetic reasons the books forming such a stack must be arranged in nonincreasing order of spine height. Their total thickness may not exceed the height of the bookshelf. The total thickness of the upright books and the width of the stack may not exceed the width of the bookshelf.
The books in Sample $1$ can be arranged like this:
Input
The input consists of:
-
One line with integers $N$, $H$, $W$ ($2\leq N\leq 100$, $130 \leq H\leq 350$, $300\leq W\leq 900$), the number of books you want to display, the height of the bookshelf in millimeters, and the width of the bookshelf in millimeters,
-
$N$ lines, one for each book, with two integers $h$, $t$ ($76\leq h\leq 483$, $5\leq t\leq 60$), the book’s spine height and thickness in millimeters. On its own, every book fits on the shelf either standing up or on its side, so we also have $h\leq \max (W, H)$.
Output
Output two lines.
The first line starts with the word “upright”, followed by the indices of the upright books. The second line starts with the word “stacked”, followed by the indices of the books in the stack, in order from bottom to top. There must be at least one upright book and at least one stacked book. Books are indexed $1$, $\ldots $, $N$.
If there is more than one solution, you may output any one of them. If no such arrangement is possible, print “impossible”.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 250 350 178 32 200 60 297 50 |
upright 1 stacked 3 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 300 300 290 60 290 60 |
impossible |
