Usaco Nov08 Gold

Part of USACO Nov08

**********************************************************************
                           GOLD PROBLEMS
**********************************************************************
                  Four problems numbered 1 through 4
**********************************************************************

Problem 1: Mixed Up Cows [Don Piele, 2007]

Each of Farmer John's N (4 <= N <= 16) cows has a unique serial
number S_i (1 <= S_i <= 25,000). The cows are so proud of it that
each one now wears her number in a gangsta manner engraved in large
letters on a gold plate hung around her ample bovine neck.

Gangsta cows are rebellious and line up to be milked in an order
called 'Mixed Up'. A cow order is 'Mixed Up' if the sequence of
serial numbers formed by their milking line is such that the serial
numbers of every pair of consecutive cows in line differs by more
than K (1 <= K <= 3400). For example, if N = 6 and K = 1 then 1,
3, 5, 2, 6, 4 is a 'Mixed Up' lineup but 1, 3, 6, 5, 2, 4 is not
(since the consecutive numbers 5 and 6 differ by 1).

How many different ways can N cows be Mixed Up?

For your first 10 submissions, you will be provided with the results of
running your program on a part of the actual test data.

POINTS: 200

PROBLEM NAME: mixup2

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains a single integer that is the serial
        number of cow i: S_i

SAMPLE INPUT (file mixup2.in):

4 1
3
4
2
1

OUTPUT FORMAT:

* Line 1: A single integer that is the number of ways that N cows can
        be 'Mixed Up'. The answer is guaranteed to fit in a 64 bit
        integer.

SAMPLE OUTPUT (file mixup2.out):

2

OUTPUT DETAILS:

The 2 possible Mixed Up arrangements are:
3 1 4 2
2 4 1 3

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

Problem 2: Cheering up the Cows [David Benjamin and Jacob Steinhardt, 2008]

Farmer John has grown so lazy that he no longer wants to continue
maintaining the cow paths that currently provide a way to visit
each of his N (5 <= N <= 10,000) pastures (conveniently numbered
1..N). Each and every pasture is home to one cow. FJ plans to remove
as many of the P (N-1 <= P <= 100,000) paths as possible while keeping
the pastures connected. You must determine which N-1 paths to keep.

Bidirectional path j connects pastures S_j and E_j (1 <= S_j <= N;
1 <= E_j <= N; S_j != E_j) and requires L_j (0 <= L_j <= 1,000) time
to traverse. No pair of pastures is directly connected by more than
one path.

The cows are sad that their transportation system is being reduced.
You must visit each cow at least once every day to cheer her up.
Every time you visit pasture i (even if you're just traveling
through), you must talk to the cow for time C_i (1 <= C_i <= 1,000).

You will spend each night in the same pasture (which you will choose)
until the cows have recovered from their sadness. You will end up
talking to the cow in the sleeping pasture at least in the morning
when you wake up and in the evening after you have returned to
sleep.

Assuming that Farmer John follows your suggestions of which paths
to keep and you pick the optimal pasture to sleep in, determine the
minimal amount of time it will take you to visit each cow at least
once in a day.

For your first 10 submissions, you will be provided with the results of
running your program on a part of the actual test data.

POINTS: 300

PROBLEM NAME: cheer

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains a single integer: C_i

* Lines N+2..N+P+1: Line N+j+1 contains three space-separated
        integers: S_j, E_j, and L_j

SAMPLE INPUT (file cheer.in):

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

INPUT DETAILS:

              +-(15)-+
             /        \
            /          \
     1-(5)-2-(5)-3-(6)--5
            \   /(17)  /
         (12)\ /      /(12)
              4------+

OUTPUT FORMAT:

* Line 1: A single integer, the total time it takes to visit all the
        cows (including the two visits to the cow in your
        sleeping-pasture)

SAMPLE OUTPUT (file cheer.out):

176

OUTPUT DETAILS:

Keep these paths:

     1-(5)-2-(5)-3      5
            \          /
         (12)\        /(12)
             *4------+

Wake up in pasture 4 and visit pastures in the order 4, 5, 4, 2,
3, 2, 1, 2, 4 yielding a total time of 176 before going back to
sleep.

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

Problem 3: Light Switching [LongFan, 2008]

Farmer John tries to keep the cows sharp by letting them play with
intellectual toys. One of the larger toys is the lights in the barn.
Each of the N (2 <= N <= 100,000) cow stalls conveniently numbered
1..N has a colorful light above it.

At the beginning of the evening, all the lights are off. The cows
control the lights with a set of N pushbutton switches that toggle
the lights; pushing switch i changes the state of light i from off
to on or from on to off.

The cows read and execute a list of M (1 <= M <= 100,000) operations
expressed as one of two integers (0 <= operation <= 1).

The first kind of operation (denoted by a 0 command) includes two
subsequent integers S_i and E_i (1 <= S_i <= E_i <= N) that indicate
a starting switch and ending switch. They execute the operation by
pushing each pushbutton from S_i through E_i inclusive exactly once.

The second kind of operation (denoted by a 1 command) asks the cows
to count how many lights are on in the range given by two integers
S_i and E_i (1 <= S_i <= E_i <= N) which specify the inclusive range
in which the cows should count the number of lights that are on.

Help FJ ensure the cows are getting the correct answer by processing
the list and producing the proper counts.

POINTS: 300

PROBLEM NAME: lites

INPUT FORMAT:

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

* Lines 2..M+1: Each line represents an operation with three
        space-separated integers: operation, S_i, and E_i

SAMPLE INPUT (file lites.in):

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

INPUT DETAILS:

Four lights; five commands. Here is the sequence that should
be processed:
     Lights
            1 2 3 4
  Init:     O O O O   O = off  * = on
  0 1 2 ->  * * O O  toggle lights 1 and 2
  0 2 4 ->  * O * *
  1 2 3 ->  1        count the number of lit lights in range 2..3
  0 2 4 ->  * * O O  toggle lights 2, 3, and 4
  1 1 4 ->  2        count the number of lit lights in the range 1..4

OUTPUT FORMAT:

* Lines 1..number of queries: For each output query, print the count
        as an integer by itself on a single line.

SAMPLE OUTPUT (file lites.out):

1
2

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

Problem 4: Toys [Chen Hu, 2006]

Bessie's birthday is coming up, and she wishes to celebrate for the
next D (1 <= D <= 100,000; 70% of testdata has 1 <= D <= 500) days.
Cows have short attention spans so Bessie wants to provide toys to
entertain them. She has calculated that she will require T_i (1 <=
T_i <= 50) toys on day i.

Bessie's kindergarten provides many services to its aspiring bovine
programmers, including a toy shop which sells toys for Tc (1 <= Tc
<= 60) dollars. Bessie wishes to save money by reusing toys, but
Farmer John is worried about transmitting diseases and requires
toys to be disinfected before use. (The toy shop disinfects the
toys when it sells them.)

The two disinfectant services near the farm provide handy complete
services. The first one charges C1 dollars and requires N1 nights
to complete; the second charges C2 dollars and requires N2 nights
to complete (1 <= N1 <= D; 1 <= N2 <= D; 1 <= C1 <= 60; 1 <= C2 <=
60). Bessie takes the toys to the disinfecters after the party and
can pay and pick them back up the next morning if one night service
is rendered, or on later mornings if more nights are required for
disinfecting.

Being an educated cow, Bessie has already learned the value of
saving her money. Help her find the cheapest way she can provide
toys for her party.

POINTS: 400

PROBLEM NAME: toy

INPUT FORMAT:

* Line 1: Six space-separated integers: D, N1, N2, C1, C2, Tc

* Lines 2..D+1: Line i+1 contains a single integer: T_i

SAMPLE INPUT (file toy.in):

4 1 2 2 1 3
8
2
1
6

INPUT DETAILS:

Bessie wishes to party for 4 days, and requires 8 toys the first day, 2
toys the second, 1 toy the third, and 6 toys on the fourth day. The
first disinfectant service takes 1 day and charges $2, and the
second takes 2 days and charges $1. Buying a new toy costs $3.

OUTPUT FORMAT:

* Line 1: The minimum cost to provide safe and sanitary toys for
        Bessie's birthday parties.

SAMPLE OUTPUT (file toy.out):

35

OUTPUT DETAILS:

Day 1   Purchase 8 toys in the morning for $24; party in the
 afternoon. Take 2 toys to the fast cleaner (overnight) and
 the other 6 toys to the slow cleaner (two nights).

Day 2   Pick up the two toys at the fast cleaner; pay $4. Party in
 the afternoon. Take 1 toy to the slow cleaner.

Day 3   Pick up 6 toys from the slow cleaner and pay $6. Party in
        the afternoon.

Day 4   Pick up the final remaining toy from the slow cleaner
        (bringing the number of toys onsite back to 6); pay $1.
        Party hearty with the realization that a minimum amount of
        money was spent.

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