Usaco Oct07 Gold

Part of USACO October 2007

``````**********************************************************************
GOLD PROBLEMS
**********************************************************************
Two problems numbered 1 through 2
**********************************************************************

Problem 1: Cow Cash [Traditional, 2003]

The cows have not only created their own government but they have
chosen to create their own money system. In their own rebellious
come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes
with a 2 unit coin thrown in for good measure.

The cows want to know how many different ways it is possible to
dispense a certain amount of money using various coin systems.  For
instance, using a system with values {1, 2, 5, 10, ...} it is
possible to create 18 units several different ways, including: 18x1,
9x2, 8x2+2x1, 3x5+2+1, and many others.

Write a program to compute how many ways to construct a given amount
of money N (1 <= N <= 10,000) using V (1 <= V <= 25) coins. It is
guaranteed that the total will fit into both a signed 'long long'
integer (C/C++), 'Int64' (Pascal), and 'long' integers in Java.

PROBLEM NAME: money

INPUT FORMAT:

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

* Lines 2..V+1: Each line contains an integer that is an available
coin value

SAMPLE INPUT (file money.in):

3 10
1
2
5

OUTPUT FORMAT:

* Line 1: A single line containing the total number of ways to
construct N money units using V coins

SAMPLE OUTPUT (file money.out):

10

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

Problem 2: Super Paintball [Aram Shatakhtsyan, 2007]

The cows have purchased a Super Paintball Deluxe game set from
Tycow, the cow-toy manufacturer. Bessie, knowing you can help, has
partitioned the pasture into a set of N x N unit squares (1 <= N
<= 100) and compiled a list of the K (1 <= K <= 100,000) locations
(1 <= R_i <= N; 1 <= C_i <= N) of every one of her opponents in the
Paintball game.

This paintball game features a paintball gun that can shoot paintballs
in any of eight directions: north, south, east, west, and the
diagonals that split those directions exactly (northeast, southeast,
northwest, southwest).

Bessie wants you to tell her the total number of squares she can
occupy and still be able to shoot all of her opponents (she can
even shoot them if she shares the same square as they occupy!).

PROBLEM NAME: paint2

INPUT FORMAT:

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

* Lines 2..K+1: Line i+1 describes cow i's location with two
space-separated integers: R_i and C_i

SAMPLE INPUT (file paint2.in):

4 3
2 1
2 3
4 1

INPUT DETAILS:

The pasture has 4 rows and 4 columns. Bessie needs to shoot cows
at (2,1), (2,3), and (4,1):
. . . .
C . C .
. . . .   <---  Cow locations
C . . .

OUTPUT FORMAT:

* Line 1: A single integer that tells how many different locations
Bessie may occupy if she is to be able to shoot any cow
according to the shooting rules.

SAMPLE OUTPUT (file paint2.out):

5

OUTPUT DETAILS:

Bessie can occupy any of these cells: (2,1), (2,3), (3,2), (4,1),
and (4,3). The diagram below notates possibly shared spaces by '*':
. . . .           . . . .
B . B .   ---\    * . * .
. B . .   ---/    . B . .
B . B .           * . B .
Potential Bessie     Bessie &amp; Cows
Locations

**********************************************************************```
```
page revision: 4, last edited: 08 Jul 2011 02:45