Problems - 2000 Winter Open, Orange
PROBLEM 5: Making Change [Traditional] 
Given the amount of a purchase (1 <= P <= 99) in cents, determine the way to make "change for a dollar" for that purchase. Use four standard US coin denominations: 1, 5, 10, and 25. The way to make change uses the least number coins.

INPUT FORMAT:

A single line with one integer, P, the amount of the purchase.

SAMPLE INPUT (file INPUT.TXT):

43

OUTPUT FORMAT:

A single line with four integers telling respectively how many 25 cent, 10 cent, 5 cent, and 1 cent pieces to give as change.

SAMPLE OUTPUT (file OUTPUT.TXT):

2 0 1 2

[Problem|Data|Solutions]

PROBLEM 6: N Queens [Traditional, Rob Kolstad]
Given an N x N chessboard, determine the number of ways N queens can be placed on the chessboard such that no queen attacks any other queen. Count rotations and reflections as distinct solutions.

INPUT FORMAT:

A single line with one integer: 5 <= N <= 12, the length of a side of the board.

SAMPLE INPUT (file INPUT.TXT):

8

OUTPUT FORMAT:

A single line with an integer telling how many possible ways N queens can be configured without attacking each other.

SAMPLE OUTPUT (file OUTPUT.TXT):

92

[Problem|Data|Solutions]

PROBLEM 7: Big Multiplications [Traditional]
Given two integers of 100 or fewer digits, determine their product. An integer might include not only digits but also a leading minus sign, if the integer is negative. Input integers contain no leading zeroes.

INPUT FORMAT:

Two lines, each with as many as 100 digits.

SAMPLE INPUT (file INPUT.TXT):

1111111111
9999999999

OUTPUT FORMAT:

A single line with the integer product expressed using the same rules as the input.

SAMPLE OUTPUT (file OUTPUT.TXT):

11111111108888888889

[Problem|Data|Solutions]

PROBLEM 8: Garage Sailing [Hal Burch]
The cows have boarded their station wagon to head to town for their annual shopping trip at garage sales. They have peculiar tastes and shop only for artistic objects that are pretty much the same size.

While peculiar, their tastes are impeccable and they have the uncanny ability to know exactly how much a given object will fetch on the open market. Sometimes, they can sell the objects for a profit.

Given the labeled price and the actual value for a set of objects, calculate the greatest possible profit the cows can make, given that only K of the objects will fit in the station wagon. Of course, the cows can buy only one of each type of object.

INPUT FORMAT:

Line 1: two integers:
K, 1 <= K <= 100, the number of objects that will fit in the station wagon
N, 1 <= N <= 100, the number of objects at the sale
Lines 2..N+1: two space-separated integers denoting respectively the price of the object at the garage sale and the price of the object on the open market
SAMPLE INPUT (file INPUT.TXT):

2 5
4 3
5 6
6 9
7 12
8 7
OUTPUT FORMAT:

A single line containing one integer, the largest possible profit given the constraints.

SAMPLE OUTPUT (file OUTPUT.TXT):

8

[Problem|Data|Solutions]