Usaco Open08 Silver

Part of USACO Open08

**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Four problems numbered 6 through 9
**********************************************************************

Problem 6: Roads Around The Farm [Aram Shatakhtsyan, 2007]

Farmer John's cows have taken an interest in exploring the territory
around the farm. Initially, all N (1 <= N <= 1,000,000,000) cows
commence traveling down a road in one big group. Upon encountering
a fork in the road, the group sometimes chooses to break into two
smaller (nonempty) groups with each group continuing down one of
the roads.  When one of those groups arrives at another fork, it
might split again, and so on.

The cows have crafted a peculiar way of splitting: if they can split
into two groups such that the sizes of the groups differ by exactly
K (1 <= K <= 1000), then they will split in that way; otherwise,
they stop exploring and just start grazing peacefully.

Assuming that there will always be new forks in the road, compute
the final number of groups of peacefully grazing cows.

PROBLEM NAME: ratf

INPUT FORMAT:

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

SAMPLE INPUT (file ratf.in):

6 2

INPUT DETAILS:

There are 6 cows and the difference in group sizes is 2.

OUTPUT FORMAT:

* Line 1: A single integer representing the number of groups of
        grazing cows

SAMPLE OUTPUT (file ratf.out):

3

OUTPUT DETAILS:

There are 3 final groups (with 2, 1, and 3 cows in them).

   6
  / \
 2   4
    / \
   1   3

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

Problem 7: Word Power [Jeffrey Wang, 2007]

Farmer John wants to evaluate the quality of the names of his N (1
<= N <= 1000) cows. Each name is a string with no more than 1000
characters, all of which are non-blank.

He has created a set of M (1 <= M <= 100) 'good' strings (no
longer than 30 characters and fully non-blank). If the sequence
letters of a cow's name contains the letters of a 'good' string in
the correct order as a subsequence (i.e., not necessarily all next
to each other), the cow's name gets 1 quality point.

All strings is case-insensitive, i.e., capital letters and lower
case letters are considered equivalent.  For example, the name "Bessie"
contains the letters of "Be", "sI", "EE", and "Es" in the correct
order, but not "is" or "eB". Help Farmer John determine the number
of quality points in each of his cow's names.

PROBLEM NAME: wordpow

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains a string that is the name of the ith
        cow

* Lines N+2..N+M+1: Line N+i+1 contains the ith good string

SAMPLE INPUT (file wordpow.in):

5 3
Bessie
Jonathan
Montgomery
Alicia
Angola
se
nGo
Ont

INPUT DETAILS:

There are 5 cows, and their names are "Bessie", "Jonathan",
"Montgomery", "Alicia", and "Angola". The 3 good strings are "se",
"nGo", and "Ont".

OUTPUT FORMAT:

* Lines 1..N+1: Line i+1 contains the number of quality points of the
        ith name

SAMPLE OUTPUT (file wordpow.out):

1
1
2
0
1

OUTPUT DETAILS:

"Bessie" contains "se", "Jonathan" contains "Ont", "Montgomery" contains
both "nGo" and "Ont", Alicia contains none of the good strings, and
"Angola" contains "nGo".

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

Problem 8: Cow Cars [Neal Wu, 2007]

N (1 <= N <= 50,000) cows conveniently numbered 1..N are driving
in separate cars along a highway in Cowtopia. Cow i can drive in
any of M different high lanes (1 <= M <= N) and can travel at a
maximum speed of S_i (1 <= S_i <= 1,000,000) km/hour.

After their other bad driving experience, the cows hate collisions
and take extraordinary measures to avoid them. On this highway, cow
i reduces its speed by D (0 <= D <= 5,000) km/hour for each cow in
front of it on the highway (though never below 0 km/hour). Thus,
if there are K cows in front of cow i, the cow will travel at a
speed of max[S_i - D * K, 0]. While a cow might actually travel
faster than a cow directly in front of it, the cows are spaced far
enough apart so crashes will not occur once cows slow down as
described,

Cowtopia has a minimum speed law which requires everyone on the
highway to travel at a a minimum speed of L (1 <= L <= 1,000,000)
km/hour so sometimes some of the cows will be unable to take the
highway if they follow the rules above. Write a program that will
find the maximum number of cows that can drive on the highway while
obeying the minimum speed limit law.

PROBLEM NAME: cowcar

INPUT FORMAT:

* Line 1: Four space-separated integers: N, M, D, and L

* Lines 2..N+1: Line i+1 describes cow i's initial speed with a single
        integer: S_i

SAMPLE INPUT (file cowcar.in):

3 1 1 5
5
7
5

INPUT DETAILS:

There are three cows with one lane to drive on, a speed decrease
of 1, and a minimum speed limit of 5.

OUTPUT FORMAT:

* Line 1: A single integer representing the maximum number of cows
        that can use the highway

SAMPLE OUTPUT (file cowcar.out):

2

OUTPUT DETAILS:

Two cows are possible, by putting either cow with speed 5 first and the cow
with speed 7 second.

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

Problem 9: Clear And Present Danger [Jeffrey Wang, 2007]

Farmer John is on a boat seeking fabled treasure on one of the N
(1 <= N <= 100) islands conveniently labeled 1..N in the Cowribbean
Sea.

The treasure map tells him that he must travel through a certain
sequence A_1, A_2, ..., A_M of M (2 <= M <= 10,000) islands, starting
on island 1 and ending on island N before the treasure will appear
to him. He can visit these and other islands out of order and even
more than once, but his trip must include the A_i sequence in the
order specified by the map.

FJ wants to avoid pirates and knows the pirate-danger rating (0 <=
danger <= 100,000) between each pair of islands. The total danger
rating of his mission is the sum of the danger ratings of all the
paths he traverses.

Help Farmer John find the least dangerous route to the treasure
that satisfies the treasure map's requirement.

PROBLEM NAME: danger

INPUT FORMAT:

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

* Lines 2..M+1: Line i+1 describes the i_th island FJ must visit with
        a single integer: A_i

* Lines M+2..N+M+1: Line i+M+1 contains N space-separated integers
        that are the respective danger rating of the path between
        island i and islands 1, 2, ..., and N, respectively. The ith
        integer is always zero.

SAMPLE INPUT (file danger.in):

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

INPUT DETAILS:

There are 3 islands and the treasure map requires Farmer John to
visit a sequence of 4 islands in order: island 1, island 2, island
1 again, and finally island 3. The danger ratings of the paths are
given: the paths (1, 2); (2, 3); (3, 1) and the reverse paths have
danger ratings of 5, 2, and 1, respectively.

OUTPUT FORMAT:

* Line 1: The minimum danger that Farmer John can encounter while
        obtaining the treasure.

SAMPLE OUTPUT (file danger.out):

7

OUTPUT DETAILS:

He can get the treasure with a total danger of 7 by traveling in
the sequence of islands 1, 3, 2, 3, 1, and 3. The cow map's requirement
(1, 2, 1, and 3) is satisfied by this route. We avoid the path
between islands 1 and 2 because it has a large danger rating.

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