Usaco Feb09 Silver

Part of USACO Feb09

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

Problem 6: The Leprechaun [Adopted from BOI'98, 2008]

Imagine Bessie's surprise as she spied a leprechaun prancing through
the north pasture. Being no one's fool, she charged at the leprechaun
at captured him with her prehensile hooves.

"One wish, bovine one. That's all I have for cows," he said.

"Riches," Bessie said dreamily. "The opportunity for riches."

Leprechauns never grant precisely the easiest form of their captor's
wishes. As the smoke cleared from the location of a loud explosion,
a shimmering donut spun slowly over the verdant green fields.

"I have made you a torus," the leprechaun cooed. "And on that torus
is an N x N matrix (1 <= N <= 200) of integers in the range
-1,000,000..1,000,000 that will determine the magnitude of your
riches. You must find the sequence of contiguous integers all in
one row, one column, or on one diagonal that yields the largest sum
from among all the possible sequences on the torus."

Bessie pondered for a moment and realized that the torus was a
device for "wrapping" the columns, rows, and diagonals of a matrix
so that one could choose contiguous elements that "wrapped around"
the side or top edge.

Bessie will share the matrix with you.  Determine the value of the
largest possible sum (which requires choosing at least one matrix
element).

By way of example, consider the 4 x 4 matrix on the left below that
has all the elements from one exemplary "wrapped" diagonal marked:

           8  6  6* 1           8  6* 6  1
          -3  4  0  5*         -3  4  0  5
           4* 2  1  9           4  2  1  9*
           1 -9* 9 -2           1 -9  9*-2

The marked diagonal of the right-hand matrix includes two nines
(the highest available number) and a six for a total of 24. This
is the best possible sum for this matrix and includes only three
of the four possible elements on its diagonal.

PROBLEM NAME: lepr

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains N space-separated integers that
        compose row i of the matrix

SAMPLE INPUT (file lepr.in):

4
8 6 6 1
-3 4 0 5
4 2 1 9
1 -9 9 -2

OUTPUT FORMAT:

* Line 1: A single integer that is the largest possible sum computable
        using the rules above

SAMPLE OUTPUT (file lepr.out):

24

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

Problem 7: Surround the Islands [Fatih Gelgi, 2008]

Farmer John has bought property in the Caribbean and is going to
try to raise dairy cows on a big farm composed of islands. Set in
his ways, he wants to surround all the islands with fence.

Each island in the farm has the shape of a polygon. He fences the
islands one side at a time (between a consecutive pair of vertices)
and proceeds clockwise around a given island with his fencing
operations. Since he wants to fence all the islands, he must at
some point travel to any other islands using a boat.

He can start fencing at any vertex and, at any vertex he encounters,
travel to some vertex on another island, fence all the way around it, and
then IMMEDIATELY return back to the same vertex on the original island
using the same path he traveled before. Each boat trip has a cost defined
by a supplied matrix.

The islands are described by a set of N (3 <= N <= 500) pairs of
vertices V1,V2 (1 <= V1 <= N; 1 <= V2 <= N) although you must figure
out how to assemble them into islands. The vertices are conveniently
numbered 1..N.

The cost of traveling by boat between each pair of vertices is given
by a symmetric cost matrix whose elements fall in the range 0..1000.

What is the minimum cost of surrounding the islands with the fence?

PROBLEM NAME: surround

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Each line describes an island's border with two
        space-separated integers: V1 and V2

* Lines N+2..2*N+1: Line i-N-1 contains N integers that describe row i
        of the cost matrix: Row_i

SAMPLE INPUT (file surround.in):

12
1 7
7 3
3 6
6 10
10 1
2 12
2 9
8 9
8 12
11 5
5 4
11 4
0 15 9 20 25 8 10 13 17 8 8 7
15 0 12 12 10 10 8 15 15 8 8 9
9 12 0 25 20 18 16 14 13 7 12 12
20 12 25 0 8 13 14 15 15 10 10 10
25 10 20 8 0 16 20 18 17 18 9 11
8 10 18 13 16 0 10 9 11 10 8 12
10 8 16 14 20 10 0 18 20 6 16 15
13 15 14 15 18 9 18 0 5 12 12 13
17 15 13 15 17 11 20 5 0 22 8 10
8 8 7 10 18 10 6 12 22 0 11 12
8 8 12 10 9 8 16 12 8 11 0 9
7 9 12 10 11 12 15 13 10 12 9 0

INPUT DETAILS:

  1        10            4
    xxxxxxx              x
   xxxxxxxxx            xxxx
7 xxxxxxxxxxx 6        xxxxxxx
 xxxxxxxxxxx       11 xxxxxxxxxx 5
  xxxxxxx
   xxx
  3         12 xxxxxxx 2
              xxxxxxxx
              xxxxxxxx
             xxxxxxxxx
             xxxxxxxxx
            xxxxxxxxxx
            xxxxxxxxxx
          8 xxxxxxxxxx 9

The example describes three islands: {1,7,3,6,10}, {4,5,11} and
{2,9,8,12}. The travel costs are provided as a matrix. For example,
the travel cost from vertex 1 to 2 is 15.

OUTPUT FORMAT:

* Line 1: A single integer that specifies the minimum cost of building
        the fence

SAMPLE OUTPUT (file surround.out):

30

OUTPUT DETAILS:

There is more than one solution. One is: FJ starts from vertex 3
then 7 and stops at 1, travels to 11 followed by 4,5,11. He then
returns back to 1, and travels to 12 followed by 2,9,8,12. Finally,
he returns back to 1 and continues with 10,6,3,7. The costs are 8
* 2 = 16 for traveling from 1 to 11 and returning back, and 7 * 2
= 14 for traveling from 1 to 12 and back -- a total cost of 30.

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

Problem 8: Bulls and Cows [Neal Wu, 2008]

Farmer John wants to position N (1 <= N <= 100,000) cows and bulls
in a single row to present at the annual fair.

FJ has observed that the bulls have been quite pugnacious lately;
if two bulls too close together in the line, they will argue and
begin to fight, ruining the presentation. Ever resourceful, FJ
calculated that any two bulls must have at least K (0 <= K < N)
cows between them in order to avoid a fight.

FJ would like you to help him by counting the number of possible
sequences of N bulls and cows that avoid any fighting. FJ considers
all bulls the to be the same and all cows to be the same; thus, two
sequences are only different if they have different kinds of cattle
in some position.

PROBLEM NAME: bullcow

INPUT FORMAT:

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

SAMPLE INPUT (file bullcow.in):

4 2

INPUT DETAILS:

FJ wants a row of 4 cattle, but any two bulls must have at least
two cows in between them.

OUTPUT FORMAT:

* Line 1: A single integer representing the number of ways FJ could
        create such a sequence of cattle. Since this number can be
        quite large, output the result modulo 5,000,011.

SAMPLE OUTPUT (file bullcow.out):

6

OUTPUT DETAILS:

The following are the six possible sequences FJ could create (note that 'C'
stands for cow and 'B' stands for bull):
CCCC
BCCC
CBCC
CCBC
CCCB
BCCB

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