**********************************************************************
BRONZE PROBLEMS
**********************************************************************
Three problems numbered 11 through 13
**********************************************************************
Problem 11: Qualified Primes [Kolstad/Ho, 2007]
Farmer John has begun branding the cows with sequential prime
numbers. Bessie has noticed this and is curious about the occurrence
of various digits in those brands.
Help Bessie determine the number of primes in the inclusive range
A..B (1 <= A <= B <= 4,000,000; B <= A + 1,000,000; one test case
has B <= A + 2,000,000 ) that contain a supplied digit D.
A prime is a positive integer with exactly two divisors (1 and
itself). The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and,
29.
PROBLEM NAME: qprime
INPUT FORMAT:
* Line 1: Three space-separated integers: A, B, and D
SAMPLE INPUT (file qprime.in):
10 15 3
INPUT DETAILS:
How many primes in the range 10..15 contain the digit 3?
OUTPUT FORMAT:
* Line 1: The count of primes in the range that contain the digit D.
SAMPLE OUTPUT (file qprime.out):
1
OUTPUT DETAILS:
Just 13 in this range contains a '3'.
**********************************************************************
Problem 12: Making Change [Traditional, 2007]
Poor Bessie has taken a job in the convenience store located just
over the border in Slobbovia. Slobbovians use different coinages
than the USA; their coin values change day-by-day!
Help Bessie make optimal change for Slobbovian shoppers. You will
need to create C (1 <= C <= 1000) cents of change using N (1 <= N
<= 10) coins of various values. All test cases will be solvable
using the supplied coins.
If 5 coins of values 50, 25, 10, 5, and 1 were available, Bessie
would make optimum change (minimal coins) of 93 cents by using 1 x
50, 1 x 25, 1 x 10, 1 x 5, and 3 x 1 coins (a total of 7 coins).
How hard could it be? The final two test cases will be challenging.
PROBLEM NAME: change
INPUT FORMAT:
* Line 1: Two space-separate integers: C and N
* Lines 2..N+1: Each line contains a single unique integer that is a
coin value that can be used to create change
SAMPLE INPUT (file change.in):
93 5
25
50
10
1
5
OUTPUT FORMAT:
* Line 1: A single integer that is the minimum number of coins to
create C cents
SAMPLE OUTPUT (file change.out):
7
**********************************************************************
Problem 13: The Bale Tower [Rob Kolstad, 2007]
Always bored with cud-chewing, the cows have invented a new game.
One cow retrieves a set of N (3 <= N <= 20) hay bales from the shed
each of which is one unit high. Each bale also has some unique width
and unique breadth.
A second cow tries to choose a set of bales to make the tallest
stack of bales in which each bale can be placed only on a bale whose
own width and breadth are smaller than the width and breadth of the
bale below. Bales can not be rotated to interchange the width and
breadth.
Help the cows determine the highest achievable tower that can be
legally built form a set of bales.
PROBLEM NAME: btwr
INPUT FORMAT:
* Line 1: A single integer, N
* Lines 2..N+1: Each line describes a bale with two space-separated
integers,respectively the width and breadth
SAMPLE INPUT (file btwr.in):
6
6 9
10 12
9 11
8 10
7 8
5 3
INPUT DETAILS:
Six bales of various widths and breadths
OUTPUT FORMAT:
* Line 1: The height of the tallest possible tower that can legally be
built from the bales.
SAMPLE OUTPUT (file btwr.out):
5
OUTPUT DETAILS:
These bales can be stacked for a total height of 5:
10 12
9 11
8 10
6 9
5 3
[another stacking exists, too]
**********************************************************************