Usaco Open09 Bronze

Part of USACO Open09

**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Four problems numbered 11 through 14
**********************************************************************

Problem 11: Time Cards [Rob Kolstad, 2009]

Farmer John wanted to improve farm productivity, so his cows now
get extra hay if they spend more time at a milking machine. To
implement this plan, he has instituted the use of time cards for
each of the N (1 <= N <= 145) cows conveniently numbered 1..N. When
a cow starts at a milking machine, she enters the start time on the
master time card. Likewise, when she leaves, she notes that on the
master time card, as well. FJ is fortunate to have enough milking
machines that he can milk every cow at the same time.

The time entries are typed into a computer file where each line
includes a cow number C (1 <= C <= N), a keyword ('START' or 'STOP'),
and the time expressed as two space-separated integers HH and MM
(0 <= HH <= 23; 0 <= MM <= 59). Cows never stay at the machine past
midnight. The timecard file is complete in the sense that every
cow's START entry contains a corresponding STOP entry later in the
input file.

Calculate the total time each cow spends at the milking machine.

By way of example, consider a time card file for just two cows. The
file includes not only the number of cows but also the total number
of time card entries, Nlines (1 <= Nlines <= 1,458).

2 6
1 START 9 0
2 START 9 30
1 STOP 10 0
2 STOP 10 15
1 START 17 0
1 STOP 17 42

Cow 1 spent times 9:00-10:00 and 17:00-17:42 at the machine for a
total of one hour and 42 minutes (1:42). Cow 2 spent time 9:30-10:15
at the machine, for a total of 45 minutes.

PROBLEM NAME: timecards

INPUT FORMAT:

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

* Lines 2..Nlines+1: Each line contains four space-separated entities:
        C, keyword, HH, and MM

SAMPLE INPUT (file timecards.in):

2 6
1 START 9 0
2 START 9 30
1 STOP 10 0
2 STOP 10 15
1 START 17 0
1 STOP 17 42

OUTPUT FORMAT:

* Lines 1..N: Line i contains two space-separated integers that are
        respectively the number of hours and minutes that cow i spends
        at the milking machine. Of course, the minutes value never
        exceeds 59.

SAMPLE OUTPUT (file timecards.out):

1 42
0 45

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

Problem 12: O Those Fads [Jarrah Lacko, 2009]

Like any other teenager, teen cows are occasionally overtaken by
fads. Sometimes it's a hula hoop or a pet rock, other times it's
Counterstrike, Pokemon, Rick Astley, or tribal tattoos on their
udders.

Mathematically, we know that a fad has an initial attractiveness
level L (1 <= L <= 50,000). Cow i has a resistance (0 <= R_i <=
1,000,000) that tells how long she can avoid a fad before having
no alternative but to participate. When a fad's attractiveness level
meets or exceeds a cow's fad resistance, then the cow will want to
participate in the fad.

Each cow who participates in a fad increases (through peer pressure)
that fad's attractiveness by some value K (1 <= K <= 2,500).

Given a population of N (1 <= N <= 100,000) cows, determine how
many will participate in a fad.

PROBLEM NAME: fads

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains cow i's a single integer that is fad
        resistance: R_i

SAMPLE INPUT (file fads.in):

5 2 3
2
6
12
5
14

INPUT DETAILS:

Five cows with fad resistances 2, 6, 12, 5, and 14. Initial fad
attractiveness is 2; peer pressure adds 3 for each attractiveness
index for each cow that participates.

OUTPUT FORMAT:

* Line 1: A single integer that is the number of cows how ultimately
        participate in the fad.

SAMPLE OUTPUT (file fads.out):

3

OUTPUT DETAILS:

The initial attraction level of 2 brings in cow #1 (whose resistance
is 2) and raises the attractiveness level to 5, thus attracting cow
#4 (whose resistance is 5) and raising the attractiveness level to
8. This attracts cow #2 (resistance: 6) and raises the attractiveness
level to 11. Neither cow #3 (resistance: 12) or cow #5 (resistance:
14) is sucked into the fad; a total of 3 cows particpate.

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

Problem 13: Good Grass [Rob Kolstad, 2009]

Bessie believes that her favorite pasture has a patch of very special
grass that is the best grass on earth. She thinks it helps cows
produce more milk.

Each of the cows has returned to her assigned grazing spot, which
is at some point in a fully populated rectilinear grid. Consider
the example on the left below where the number of rows, NR (3 <=
NR <= 100) is 6 and the number of columns, NC (3 <= NC <= 100) is
5. The spots for cows are marked with a 'C'.

Bessie actually knows the milk production P_rc (1 <= P_rc <= 100)
of each of the cows in the grid; the cows are tagged with the
production number in the grid on the right, below.

               COLUMN                      COLUMN
           1  2  3  4  5               1  2  3  4  5
         +--------------             +--------------
        1| C  C  C  C  C            1| 5  6  7  4  6
     R  2| C  C  C  C  C         R  2| 7  7  8  6  5
     O  3| C  C  C  C  C         O  3| 9  9  8  3  5
     W  4| C  C  C  C  C         W  4| 8  8  7  6  4
        5| C  C  C  C  C            5| 4  5  2  4  5
        6| C  C  C  C  C            6| 3  4  2  3  4

Bessie wants to find the location of the special grass. She intends
to do this by finding the 3 x 3 grid of cows whose total milk
production is the largest.

Find the 3 x 3 grid whose nine components sum to the greatest number
and report the value of its upper left corner (first the row, then
the column). In the grid above on the right, the largest sum is 71
found in the grid whose upper left corner (as depicted) is row 2,
column 1.

If two 3 x 3 grids have the same sum, output the one whose row
number is smallest. If more than one grid on that row has the same
sum, output the one with the lowest column number.

PROBLEM NAME: goodgrs

INPUT FORMAT:

* Line 1: Two space-separated integers: NR and NC

* Lines 2..NR+1: Line r+1 contains NC space-separated integers that
        represent row r of the pasture's grid.

SAMPLE INPUT (file goodgrs.in):

6 5
5 6 7 4 6
7 7 8 6 5
9 9 8 3 5
8 8 7 6 4
4 5 2 4 5
3 4 2 3 4

OUTPUT FORMAT:

* Line 1: A single integer that is the greatest possible sum in a 3 x
        3 square.

* Line 2: Two space-separated integers that are respectively the row
        and column of the upper left corner of the 'best' 3 x 3 square
        grid.

SAMPLE OUTPUT (file goodgrs.out):

71
2 1

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

Problem 14: Treasure Cave [Rob Kolstad, 2009]

Bessie's grandfather was a pirate who accumulated a great treasure
chest of golden plunder. He hid the treasure chest in a cave that
Bessie has recently discovered right on Farmer John's land! Just
inside the cave's entrance she found a map that told her how to get
the treasure.

The cave has P passages (3 <= P <= 5,000) conveniently numbered
1..P. The entrance is passage 1; the treasure is located in some
reachable passage T (2 <= T <= P), whose value is supplied. Passages
are all approximately the same length; each one leads to a split
where hitherto unexplored numbered passages take the inquisitive
cow deeper underground. No passage appears as the split from more
than one passage, and the map contains a total of NS splits (1 <=
NS <= 5,000).

Bessie wants to know both how far away from the entrance the treasure
lies and also which passage numbers to take to get to the treasure.

Consider the schematic representation of a cave shown below. Passage
numbers are shown close to the passage they name. For this example,
the treasure is at the end of passage number 7:

                   3/
                   /
                  +
                 / \   /5
               2/  4\ /
           1   /     +
          ----+      6\   #7    /11
               \       \ /     /
              13\       +     +
                        8\ 10/ \
                          \ /   \12
                           +
                           9\
                             \

Bessie would have to traverse passages 1, 2, 4, 6, and 7 to get to
the treasure, a total distance of 5 (which is simply the passage
count).

The input file includes a set of lines, each with a passage number
N (1 <= N <= P) and the two passages (B1 and B2; 1 <= B1 <= P; 1
<= B2 <= P) that branch off from it. Some line in the input file
will include passage number 1 and its two branches (for our example,
passages 2 and 13; likewise, passage number 8 has two branches: 9
and 10).

Tell Bessie how to get to the treasure.

PROBLEM NAME: tcave

INPUT FORMAT:

* Line 1: Line 1 contains three space-separated integers: P, NS, and T

* Lines 2..NS+1: Each line contains three space-separated integers: N,
        B1, and B2

SAMPLE INPUT (file tcave.in):

13 6 7
6 7 8
2 3 4
10 11 12
8 9 10
1 2 13
4 5 6

INPUT DETAILS:

This input describes the sample cave in text.

OUTPUT FORMAT:

* Line 1: The distance D from the entrance to the treasure

* Lines 2..D+1: Line i+1 contains a single integer that is next
        passage Bessie takes to get to the treasure.

SAMPLE OUTPUT (file tcave.out):

5
1
2
4
6
7

OUTPUT DETAILS:

As in the text.

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