Usaco Nov08 Bronze

Part of USACO Nov08

```
**********************************************************************
BRONZE PROBLEMS
**********************************************************************
Three problems numbered 11 through 13
**********************************************************************
Problem 11: Switching Lights [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 <= 500) 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 <= 2,000) operations
expressed as one of two integers (0 <= operation <= 1).
The first 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 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.
PROBLEM NAME: swtch
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 swtch.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 swtch.out):
1
2
**********************************************************************
Problem 12: Guarding the Farm [Fatih Gelgi, 2008]
The farm has many hills upon which Farmer John would like to place
guards to ensure the safety of his valuable milk-cows.
He wonders how many guards he will need if he wishes to put one on
top of each hill. He has a map supplied as a matrix of integers;
the matrix has N (1 < N <= 100) rows and M (1 < M <= 70) columns.
Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000).
Help him determine the number of hilltops on the map.
A hilltop is one or more adjacent matrix elements of the same value
surrounded exclusively by either the edge of the map or elements
with a lower (smaller) altitude. Two different elements are adjacent
if the magnitude of difference in their X coordinates is no greater
than 1 and the magnitude of differences in their Y coordinates is
also no greater than 1.
PROBLEM NAME: guard
INPUT FORMAT:
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes row i of the matrix with M
space-separated integers: H_ij
SAMPLE INPUT (file guard.in):
8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
OUTPUT FORMAT:
* Line 1: A single integer that specifies the number of hilltops
SAMPLE OUTPUT (file guard.out):
3
OUTPUT DETAILS:
There are three peaks: The one with height 4 on the left top, one of
the points with height 2 at the bottom part, and one of the points with
height 1 on the right top corner.
**********************************************************************
Problem 13: Going Once, Going Twice, Gone! [Jeffrey Wang, 2008]
The cows' slimming diet has left Farmer John with extra hay so he
has decided to hold an auction to reduce his inventory. He has N
(1 <= N <= 1,000) identical lots (each of about 100 bales) of hay;
his potential customers comprise M (1 <= M <= 1,000) other farmers
in the area.
Each farmer i tells Farmer John how much he is willing to pay P_i
(1 <= P_i <= 1,000,000) for a lot of hay. Each of the farmers
wishes to purchase a single lot of hay.
To make sure the other farmers do not get jealous of each other,
Farmer John decides that he must sell the lots of hay at a fixed
price to each customer who is willing to pay at least that price;
the rest will decline the purchase.
Help Farmer John determine the smallest price he should set on a
lot of hay to maximize the amount of money he makes.
PROBLEM NAME: auction
INPUT FORMAT:
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 contains a single integer: P_i
SAMPLE INPUT (file auction.in):
5 4
2
8
10
7
INPUT DETAILS:
Farmer John has 5 lots of hay. 4 farmers wish to purchase hay; they
will pay 2, 8, 10, and 7, respectively, for a lot of hay.
OUTPUT FORMAT:
* Line 1: Two space-separated integers: the smallest price that Farmer
John should choose to maximize his revenue and the amount of
money he takes in.
SAMPLE OUTPUT (file auction.out):
7 21
OUTPUT DETAILS:
Farmer John should set the price at 7 so that 3 of the farmers will
be willing to pay for a lot of hay, and he will earn 21.
**********************************************************************
```

page revision: 1, last edited: 06 Jun 2009 21:41