Usaco Open12 Silver

Part of USACO Open12

**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Three problems numbered 1 through 3
**********************************************************************

Problem 1: Unlocking Blocks (Silver) [Brian Dean, 2012]

A little-known fact about cows is that they love puzzles! For Bessie's
birthday, Farmer John gives her an interesting mechanical puzzle for her to
solve.  The puzzle consists of three solid objects, each of which is built
from 1x1 unit squares glued together.  Each of these objects is a
"connected" shape,  in the sense that you can get from one square on the
object to any other square on the object by stepping north, south, east, or
west, through squares on the object.

An object can be moved by repeatedly sliding it either north, south,
east, or west one unit.  The goal of the puzzle is to move the objects
so that they are separated -- where their bounding boxes no longer
share any positive overlap with each-other.  Given the shapes and
locations of the three objects, your task is to help Bessie decide
what is the minimum number of individual slides required to separate
the objects.

fig_unlock.png
PROBLEM NAME: unlock

INPUT FORMAT:

* Line 1: Three space-separated integers: N1, N2, and N3, describing
        respectively the number of unit squares making up objects 1,
        2, and 3.

* Lines 2..1+N1: Each of these lines describes the (x,y) location of
        the south-west corner of single square that is part of object
        1.  All coordinates lie in the range 0..9.

* Lines 2+N1..1+N1+N2: Each of these lines describes the (x,y)
        location of the south-west corner of single square that is
        part of object 2.  All coordinates lie in the range 0..9.

* Lines 2+N1+N2..1+N1+N2+N3: Each of these lines describes the (x,y)
        location of the south-west corner of single square that is
        part of object 3.  All coordinates lie in the range 0..9.

SAMPLE INPUT (file unlock.in):

12 3 5
0 0
1 0
2 0
3 0
3 1
0 1
0 2
0 3
0 4
1 4
2 4
3 4
2 1
2 2
1 2
2 3
3 3
4 3
4 4
4 2

INPUT DETAILS:

Object 1 is made from 12 squares, object 2 is made from 3 squares, and
object 3 is made from 5 squares.  The shapes of the objects are those in
the figure above.

OUTPUT FORMAT:

* Line 1: The minimum number of moves necessary to separate the three
objects, or -1 if the objects cannot be separated.

SAMPLE OUTPUT (file unlock.out):

5

OUTPUT DETAILS:

If we slide object 3 to the east by one position, then slide object 2
north by one position, then slide object 1 west by three positions,
then the bounding boxes of the three objects will no longer share any
overlap in common.

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

Problem 2: Bookshelf (Silver) [Neal Wu / Traditional, 2012]

When Farmer John isn't milking cows, stacking haybales, lining up his cows,
or building fences, he enjoys sitting down with a good book.  Over the
years, he has collected N books (1 <= N <= 2,000), and he wants to build
a new set of bookshelves to hold them all.  

Each book i has a width W(i) and height H(i).  The books need to be added
to a set of shelves in order; for example, the first shelf should contain
books 1...k for some k, the second shelf should start with book k+1, and so
on.  Each shelf can have a total width of at most L (1 <= L <=
1,000,000,000).  The height of a shelf is equal to the height of the
tallest book on that shelf, and the height of the entire set of bookshelves
is the sum of the heights of all the individual shelves, since they are all
stacked vertically.  

Please help FJ compute the minimum possible height for the entire set of
bookshelves.

PROBLEM NAME: bookshelf

INPUT FORMAT:

* Line 1: Two space-separated integers: N and L.

* Lines 2..1+N: Line i+1 contains two space-separated integers: H(i)
        and W(i).  (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).

SAMPLE INPUT (file bookshelf.in):

5 10
5 7
9 2
8 5
13 2
3 8

INPUT DETAILS:

There are 5 books.  Each shelf can have total width at most 10.

OUTPUT FORMAT:

* Line 1: The minimum possible total height for the set of
        bookshelves.

SAMPLE OUTPUT (file bookshelf.out):

21

OUTPUT DETAILS:

There are 3 shelves, the first containing just book 1 (height 5, width 7),
the second containing books 2..4 (height 13, width 9), and the third
containing book 5 (height 3, width 8).

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

Problem 3: Running Laps [Brian Dean, 2012]

Bored with horse racing, Farmer John decides to investigate the feasibility
of cow racing as a sport.  He sets up his N cows (1 <= N <= 100,000) to run
a race of L laps around a circular track of length C.  The cows all start
at the same point on the track and run at different speeds, with the race
ending when the fastest cow has run the total distance of LC.  

FJ notices several occurrences of one cow overtaking another, and wonders
how many times this sort of "crossing event" happens during the entire
race.  More specifically, a crossing event is defined by a pair of cows
(x,y) and a time t (less than or equal to the ending time of the race),
where cow x crosses in front of cow y at time t.  Please help FJ count the
total number of crossing events during the entire race.

PROBLEM NAME: running

INPUT FORMAT:

* Line 1: Three space-separated integers: N, L, and C.  (1 <= L,C <=
        25,000).

* Lines 2..1+N: Line i+1 contains the speed of cow i, an integer in
        the range 1..1,000,000.

SAMPLE INPUT (file running.in):

4 2 100
20
100
70
1

INPUT DETAILS:

There are 4 cows running 2 laps on a circular track of length 100.  The
speeds of the cows are 20, 100, 70, and 1. 

OUTPUT FORMAT:

* Line 1: The total number of crossing events during the entire race.

SAMPLE OUTPUT (file running.out):

4

OUTPUT DETAILS:

The race lasts 2 units of time, since this is the time it takes the fastest
cow (cow 2) to finish.  Within that time, there are 4 crossing events: cow
2 overtakes cows 1 and 4, and cow 3 overtakes cows 1 and 4.

**********************************************************************
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License