Problem A: Cube Stacking [Mihai Patrascu, 2001]

Farmer John and Bessie are playing a game with N (1 <= N <= 30,000)
identical cubes labeled 1 through N. They start with N stacks, each
containing a single cube. Farmer John asks Bessie to perform P (1
<= P <= 100,000) operation.  There are two types of operations:
moves and counts.
  * In a move operation, Farmer John asks Bessie to move the stack
    containing cube X on top of the stack containing cube Y.
  * In a count operation, Farmer John asks Bessie to count the
    number of cubes on the stack with cube X that are under the
    cube X and report that value.

Write a program that can verify the results of the game.

PROBLEM NAME: cubes

INPUT FORMAT:

* Line 1: A single integer, P

* Lines 2..P+1: Each of these lines describes a legal operation. Line
        2 describes the first operation, etc.  Each line begins with a
        'M' for a move operation or a 'C' for a count operation.  For
        move operations, the line also contains two integers: X and Y.
         For count operations, the line also contains a single
        integer: X.

Note that the value for N does not appear in the input file. No move
operation will request a move a stack onto itself.

SAMPLE INPUT (file cubes.in):

6               | Six total operations
M 1 6		| 1,6 / 2 / 3 / 4 / 5 [1 is on top of 6]
C 1		| print number below cube 1: 1
M 2 4		| 1,6 / 2,4 / 3 / 5
M 2 6		| 2,4,1,6 / 3 / 5
C 3		| print number below cube 3: 0
C 4		| print number below cube 4: 2

INPUT DETAILS:

The '|' and succeeding characters show the current configuration;
they are not part of the input file.

OUTPUT FORMAT:

Print the output from each of the count operations in the same order
as the input file.

SAMPLE OUTPUT (file cubes.out):

1
0
2

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

Problem B: The Cow Lineup [Brian Dean, 2004]

Farmer John's N cows (1 <= N <= 100,000) are lined up in a row.
Each cow is labeled with a number in the range 1...K (1 <= K <=
10,000) identifying her breed.  For example, a line of 14 cows might
have these breeds:

    1 5 3 2 5 1 3 4 4 2 5 1 2 3

Farmer John's acute mathematical mind notices all sorts of properties
of number sequences like that above.  For instance, he notices that
the sequence 3 4 1 3 is a subsequence (not necessarily contiguous)
of the sequence of breed IDs above.  FJ is curious what is the
length of the shortest possible sequence he can construct out of
numbers in the range 1..K that is NOT a subsequence of the breed
IDs of his cows.  Help him solve this problem.

PROBLEM NAME: lineup

INPUT FORMAT:

* Line 1: Two integers, N and K

* Lines 2..N+1: Each line contains a single integer that is the breed
        ID of a cow. Line 2 describes cow 1; line 3 describes cow 2;
        and so on.

SAMPLE INPUT (file lineup.in):

14 5
1
5
3
2
5
1
3
4
4
2
5
1
2
3

OUTPUT FORMAT:

* Line 1: The length of the shortest sequence that is not a
        subsequence of the input

SAMPLE OUTPUT (file lineup.out):

3

OUTPUT DETAILS:

All the single digit 'sequences' appear. Each of the 25 two digit
sequences also appears. Of the three digit sequences, the sequence
2, 2, 4 does not appear.

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

Problem C: MooFest [Brian Dean, 2004]

Every year, Farmer John's N (1 <= N <= 20,000) cows attend "MooFest",
a social gathering of cows from around the world.  MooFest involves
a variety of events including haybale stacking, fence jumping, pin
the tail on the farmer, and of course, mooing.  When the cows all
stand in line for a particular event, they moo so loudly that the
roar is practically deafening.  After participating in this event
year after year, some of the cows have in fact lost a bit of their
hearing.

Each cow i has an associated "hearing" threshold v(i) (in the range
1..20,000).  If a cow moos to cow i, she must use a volume of at
least v(i) times the distance between the two cows in order to be
heard by cow i.  If two cows i and j wish to converse, they must
speak at a volume level equal to the distance between them times
max(v(i),v(j)).

Suppose each of the N cows is standing in a straight line (each cow
at some unique x coordinate in the range 1..20,000), and every pair of
cows is carrying on a conversation using the smallest possible
volume.

Compute the sum of all the volumes produced by all N(N-1)/2 pairs
of mooing cows.

PROBLEM NAME: moofest

INPUT FORMAT:

* Line 1: A single integer, N

* Lines 2..N+1: Two integers: the volume threshold and x coordinate
        for a cow.  Line 2 represents the first cow; line 3 represents
        the second cow; and so on.  No two cows will stand at the same
        location.

SAMPLE INPUT (file moofest.in):

4
3 1
2 5
2 6
4 3

OUTPUT FORMAT:

* Line 1: A single line with a single integer that is the sum of all
        the volumes of  the conversing cows.

SAMPLE OUTPUT (file moofest.out):

57

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

Problem D: Turning in Homework [Hal Burch, 2004]

Bessie must turn in her homework for her C classes (1 <= C <= 1,000)
at Moo U so that she still has time to chew the cud with her fellow
classmates as they wait for the bus to go home.

Teachers accept homework submissions only after they have finished
their classes and also cleaned the chalkboard, put away lab supplies,
and so on. The input data tells the earliest time a teacher will
accept homework.

Bessie starts at one end (distance 0) of a hallway H (1 <= H <=
1,000) meters long and walks at the rate of one meter per second
to various classrooms (in any order she chooses) to turn in her
homework.  Each classroom is located along this hallway, as well
as the door to the waiting area for the buses.

Given the location of both the exit and the classrooms and also
the teachers' schedules, determine the earliest time that Bessie
can exit the door to the waiting area for the buses.  Bessie must
turn in all her homework before exiting.  The act of turning in the
homework takes no time, by the way.

PROBLEM NAME: turnin

INPUT FORMAT:

* Line 1: Three integers: C, H, and B.  B (0 <= B <= H) is the
        distance from the hall entrance to the bus waiting area.

* Lines 2..C+1: Each line contains two integers that describe a
        classroom where homework is to be submitted. The first integer
        (0..H) is the number of meters to the classroom from the
        hallway entrance.  The second integer (0..10,000) is the first
        time (in seconds) that the teacher for that course will accept
        homework.

SAMPLE INPUT (file turnin.in):

4 10 3
8 9
4 21
3 16
8 12

OUTPUT FORMAT:

* Line 1: A single integer: the earliest second that Bessie can exit
        the door to the waiting area for the buses.

SAMPLE OUTPUT (file turnin.out):

22

OUTPUT DETAILS:

Time   Action
  0   Bessie walks to the classrooms 8 meters down the hall (at 8m)
  8   Bessie waits 1 second
  9   Bessie turns in the first set of homework 
  9   Bessie waits 3 seconds, thinking about cool hay in the summertime
 12   Bessie turns in the other homework for this location
 12   Bessie walks back to the classroom 4 meters down the hall (at 4m)
 16   Bessie waits 5 seconds, thinking of a handsome bull she once met
 21   Bessie turns in her homework
 21   Bessie walks back to the classroom 1 meters down the hall (at 3m)
 22   Bessie turns in her homework
 22   Bessie exits, since this also the location of the bus exit

Thus, Bessie can leave at time 22.  No better schedule exists.

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

Problem F: Cave Cows 1 [Brian Dean, 2004]

Few people know that cows are actually quite fond of exploring caves.  

Bessie is planning to visit her favorite cave, which has N rooms
(1 <= N <= 100) numbered 1..N and M bidirectional corridors (1 <=
M <= 1000) connecting pairs of different rooms.  Room 1 is the
entrance to the cave. Two rooms are never directly connected by
more than one corridor.

Always planning ahead, Bessie previously deposited a bale of hay
in each of K (1 <= K <= 14) different rooms so she will have food
available during her expedition.  Of course just like people, every
time Bessie consumes a bale of hay, her "fatness" index increases
by one unit.

When she enters the cave, her fatness index is 0 units. Every
corridor in the cave has a certain width; Bessie can only fit through
a corridor if her fatness index is no larger than that corridor's
width. 

Bessie wants to eat as much as possible during her trip into the
cave but wants to make sure that she does not grow too fat and trap
herself in the process (at the end of her trip she must exit the cave
at room 1).  Help her determine the maximum amount of hay she can eat.  
Note that Bessie can decide to pass through a room containing a bale of 
hay without eating the hay, if she wishes.

PROBLEM NAME: cavecow1

INPUT FORMAT:

* Line 1: Three space-separated integers: N , M, and K

* Lines 2..K+1: Each of these lines contains the index (1..N) of a
        room containing a  bale of hay.

* Lines K+2..K+M+1: Each of these lines corresponds to a bidirectional
        corridor and contains three space-separated integers: indices
        of the two rooms connected by the corridor, and the corridor's
        integer width (1..100).

SAMPLE INPUT (file cavecow1.in):

6 7 5
1
2
3
4
5
1 2 3
3 6 2
6 2 10
2 4 1
5 1 1
4 5 1
1 6 1

OUTPUT FORMAT:

* Line 1: A single integer giving the maximum number of bales of hay
        Bessie can eat  and still successfully exit the cave.

SAMPLE OUTPUT (file cavecow1.out):

4

OUTPUT DETAILS:

All corridors leaving the entrance room have width at most 3.  Thus,
returning to that room Bessie must have eaten no more than 3 bales.
Combined with the bale in that room, 4 is the maximum number of bales
that can be consumed.

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

Problem G: Cave Cows 2 [Brian Dean, 2004]

In one cave Bessie is planning to explore, a long corridor is made
up of N segments (1 <= N <= 25,000 and numbered 1..N) joined
end-to-end.  Each of these segments has a particular width which
can only be traversed by a cow whose "fatness" index is no larger
than that width.  A cow can travel along a sequence i..j of these
segments only if its fatness index is no larger than the minimum width
of all of those corridors.  Corridor widths are integers in the
range 1..1,000,000,000.

In order to plan her caving expedition, Bessie needs to answer a
collection of Q (1 <= Q <= 25,000) queries of the form "what is the
maximum fatness of a cow that can pass through the sequence i..j
of corridors?".  Please help Bessie with her dilemma.

PROBLEM NAME: cavecow2

INPUT FORMAT:

* Line 1: Two space-separated integers, N and Q

* Lines 2..N+1: Each line gives the integer width of a corridor. Line
        2 describes corridor 1; line 2 describes corridor 2; and so
        on.

* Lines N+2..N+Q+1: Each line corresponds to a query and contains two
        space-separated  integers i and j (where i < j), giving the
        indices of the corridors at  both ends of the query interval.

SAMPLE INPUT (file cavecow2.in):

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

OUTPUT FORMAT:

* Lines 1..Q: Each line contains the integer answer to a query

SAMPLE OUTPUT (file cavecow2.out):

5
38
20
5

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

Problem H: Cave Cows 3 [Brian Dean, 2004]

Farmer John's N (1 <= N <= 50,000) cows are exploring a large room
in a cave.  It is dark, and the cows communicate by mooing loudly
at each other.  Due to the strange accoustics of the room, the time
it takes for a 'moo' from one cow to reach another cow is proportional
to the "manhattan" distance between the two cows: that is, if cow
A is at location (Xa, Ya) and cow B is at location (Xb, Yb), it
takes |Xa-Xb| + |Ya-Yb| units of time for a 'moo' from cow A to
reach cow B. X and Y coordinates are all in the range (-1,000,000
.. 1,000,000).

Given the locations of the N cows, determine the maximum time over all 
pairs of cows for a 'moo' to propagate.

PROBLEM NAME: cavecow3

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Each line contains two space-separated integers,
        giving the (x,y) coordinates of a cow

SAMPLE INPUT (file cavecow3.in):

5
1 1
3 5
2 7
8 1
4 4

OUTPUT FORMAT:

* Line 1: The maximum 'moo' distance among all pairs of cows

SAMPLE OUTPUT (file cavecow3.out):

12

OUTPUT DETAILS:

The cows at (2,7) and (8,1) are separated by |2-8| + |7-1| =
6 + 6 = 12 units.

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

Problem I: Cave Cows 4 [Brian Dean, 2004]

A rockslide has trapped Bessie in her cave, and she must scale a
vertical rock wall if she is to escape!  Happily, Bessie is an
accomplished rock climber.

Think of the rock wall as a two-dimensional plane, with an x
(horizontal) and z (vertical) axis.  Bessie starts with her left
front hoof at (0,0), and she needs to climb to the top of the wall,
at z = T (1 <= T <= 200,000).

The wall has N (1 <= N <= 50,000) rocks that stick out and provide
hoofholds for Bessie.  If Bessie is currently holding on to one of
these hoofholds with her left front hoof, she can reach a new
hoofhold only if it is at most 2 units away in its x coordinate and
also at most 2 units away in its z coordinate from her current hold.
Note that Bessie can move to a hoofhold above, beside, or below
her, as long as its x and z coordinates are both within 2 units of
her current hoofhold. When she moves, her front left hoof ends up
on the new hoofhold.

Help Bessie determine if she can scale the wall (that is, if she can 
reach any hoofhold at height T), and if so, the minimum number 
of hoofholds she must use.  

PROBLEM NAME: cavecow4

INPUT FORMAT:

* Line 1: Two space-separated integers: N and T

* Lines 2..N+1: Each line contains two space-separated integers that
        represent the (x,z)  coordinates of a hoofhold.  Each x
        coordinate will be in the range  0 .. 1,000,000, and each z
        coordinate will be in the range 0 .. T.  The  initial foothold
        (0,0) does not appear in this list.

SAMPLE INPUT (file cavecow4.in):

5 3
1 2
6 3
4 1
3 2
0 2

OUTPUT FORMAT:

* Line 1: The minimum number of steps required to reach the top or -1
        if it is  impossible to reach the top.  The initial hoofhold
        at (0,0) does not  count as a step.

SAMPLE OUTPUT (file cavecow4.out):

4