**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Three problems numbered 6 through 8
**********************************************************************

Problem 6: Stall Reservations [Brian Dean, 2004]

Oh those picky N (1 <= N <= 50,000) cows! They are so picky that
each one will only be milked over some precise time interval A..B
(1 <= A <= B <= 1,000,000), which includes both times A and B.  Obviously,
FJ must create a reservation
system to determine which stall each cow can be assigned for her
milking time. Of course, no cow will share such a private moment
with other cows.

Help FJ by determining:
* The minimum number of stalls required in the barn so that each
  cow can have her private milking period
* An assignment of cows to these stalls over time

Many answers are correct for each test dataset; a program will grade
your answer.

PROBLEM NAME: reserve

INPUT FORMAT:

* Line 1: A single integer, N

* Lines 2..N+1: Line i+1 describes cow i's milking interval with two
        space-separated integers.

SAMPLE INPUT (file reserve.in):

5
1 10
2 4
3 6
5 8
4 7

OUTPUT FORMAT:

* Line 1: The minimum number of stalls the barn must have.

* Lines 2..N+1: Line i+1 describes the stall to which cow i will be
        assigned for her milking period.

SAMPLE OUTPUT (file reserve.out):

4
1
2
3
2
4

OUTPUT DETAILS:

Here's a graphical schedule for this output:

Time     1  2  3  4  5  6  7  8  9 10
Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>
Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..
Stall 3 .. .. c3>>>>>>>>> .. .. .. ..
Stall 4 .. .. .. c5>>>>>>>>> .. .. ..

Other outputs using the same number of stalls are possible.

**********************************************************************

Problem 7: Treats for the Cows [Marco Gallotta, 2005]

FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who
get money for giving vast amounts of milk. FJ sells one treat per
day and wants to maximize the money he receives over a given period
time.

The treats are interesting for many reasons:
  * The treats are numbered 1..N and stored sequentially in single
    file in a long box that is open at both ends. On any day, FJ
    can retrieve one treat from either end of his stash of treats.
  * Like fine wines and delicious cheeses, the treats improve with
    age and command greater prices.
  * The treats are not uniform: some are better and have higher
    intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000).
  * Cows pay more for treats that have aged longer: a cow will
    pay v(i)*a for a treat of age a.

Given the values v(i) of each of the treats lined up in order of
the index i in their box, what is the greatest value FJ can receive
for them if he orders their sale optimally?

The first treat is sold on day 1 and has age a=1. Each subsequent
day increases the age by 1.

PROBLEM NAME: treat

INPUT FORMAT:

* Line 1: A single integer, N

* Lines 2..N+1: Line i+1 contains the value of treat v(i)

SAMPLE INPUT (file treat.in):

5
1
3
1
5
2

INPUT DETAILS:

Five treats. On the first day FJ can sell either treat #1 (value 1) or
treat #5 (value 2).

OUTPUT FORMAT:

* Line 1: The maximum revenue FJ can achieve by selling the treats

SAMPLE OUTPUT (file treat.out):

43

OUTPUT DETAILS:

FJ sells the treats (values 1, 3, 1, 5, 2) in the following order
of indices: 1, 5, 2, 3, 4, making 1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.

**********************************************************************

Problem 8: Backward Digit Sums [Harry Wiggins, 2002]

FJ and his cows enjoy playing a mental game. They write down the
numbers from 1 to N (1 <= N <= 10) in a certain order and then sum
adjacent numbers to produce a new list with one fewer number.  They
repeat this until only a single number is left.  For example, one
instance of the game (when N=4) might go like this:

    3   1   2   4
      4   3   6
        7   9
         16

Behind FJ's back, the cows have started playing a more difficult
game, in which they try to determine the starting sequence from
only the final total and the number N.  Unfortunately, the game is
a bit above FJ's mental arithmetic capabilities.

Write a program to help FJ play the game and keep up with the cows.

PROBLEM NAME: bds

INPUT FORMAT:

* Line 1: Two space-separated integers: N and the final sum.

SAMPLE INPUT (file bds.in):

4 16

OUTPUT FORMAT:

* Line 1: An ordering of the integers 1..N that leads to the given
        sum.  If there are multiple solutions, choose the one that is
        lexicographically least, i.e., that puts smaller numbers
        first.

SAMPLE OUTPUT (file bds.out):

3 1 2 4

OUTPUT DETAILS:

There are other possible sequences, such as 3 2 1 4, but 3 1 2 4
is the lexicographically smallest.

**********************************************************************