**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Three problems numbered 11 through 13
**********************************************************************

Problem 11: Cow Yahtzee [Kolstad, 2007]

In their usual clumsy way, the cows are play a version of Yahtzee,
the dice-rolling game.  They roll N (1 <= N <= 20) dice, each having
S (1 <= S <= 8) sides.  They are curious as to the number of ways
a dice roll can meet a particular criterion (like "contains three
2's" or "contains one 2 and two 3's").

Help them learn about probability. Write a program that reads not
only N and S but also some expressions that describe their criteria.
Count the number ways the expression can be satisfied over the
entire set of all possible dice rolls (the entire set of rolls for
three two-sided dice is: {1,1,1; 1,1,2; 1,2,1; 1,2,2; 2,1,1; 2,1,2;
2,2,1; 2,2,2};

Expressions comprise combinations of a basic form that expresses
the thought "want at least W copies of result R". It looks like this:

WxR

where (0 <= W <= N and 1 <= R <= S). Each test run will supply E
expressions (1 <= E <= 20), each of which contains a number 1..10
of the basic forms separated by a '+', which means 'and' (see below).
The set of lines expresses the thought that is the 'inclusive or'
of each of the lines individually. Thus the pair of expressions
shown below means "at least three rolls of five OR both at least
one roll of 3 and also at least two rolls of 4":

3x5
1x3+2x4

Here are some of the combinations of four five-sided dice that
satisfy the above expression: 5,5,5,1; 4,5,5,5; 3,4,4,2; 3,4,4,3;
3,4,4,5; 4,4,5,3.

Programming note: Be sure to verify that you can read in two integers
from one line and a string from the next line. In some languages'
I/O schema, this is harder than it looks!

Also note that the total number of dice combinations will never
exceed 1,512,768 in the supplied test data.

PROBLEM NAME: cowyotz

INPUT FORMAT:

* Line 1: Three space-separated integers: N, S, and E

* Lines 2..E+1: Line i+1 describes expression i as above.

SAMPLE INPUT (file cowyotz.in):

4 5 2
3x5
1x3+2x4

INPUT DETAILS:

This is the encoding of the expression used as an example in the task text.

OUTPUT FORMAT:

* Line 1: A single integer that is the number of ways the
        expression(s) can be satisfied by rolling the dice in all
        combinations.

SAMPLE OUTPUT (file cowyotz.out):

63

OUTPUT DETAILS:

63 rolls satisfy the expression.

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

Problem 12: Bronze Lilypad Pond [Ho/Kolstad, 2007]

Farmer John has installed a beautiful pond for his cows' esthetic
enjoyment and exercise. The rectangular pond has been partitioned
into square cells of M rows and N columns (1 <= M <= 30; 1 <= N <=
30). Some of the cells have astonishingly sturdy lilypads; others
have rocks; the remainder are just beautiful, cool, blue water.

Bessie is practising her ballet moves by jumping from one lilypad
to another and is currently located at one of the lilypads (see the
input data for the location's specifier). She wants to travel to
another lilypad in the pond by jumping from one lilypad to another.
She can jump neither into the water nor onto a rock.

Surprising only to the uninitiated, Bessie's jumps between lilypads
always appear as a sort of chess-knight's move: move M1 (1 <= M1
<= 30) 'squares' in one direction and then M2 (1 <= M2 <= 30; M1
!= M2) more in an orthogonal direction (or perhaps M2 in one direction
and then M1 in an orthogonal direction). Bessie sometimes might
have as many as eight choices for her jump.

Given the pond layout and the format of Bessie's jumps, determine
the smallest number of leaps that Bessie must make to move from her
starting location to her final destination, a feat which is always
possible for the given test data.

PROBLEM NAME: bronlily

INPUT FORMAT:

* Line 1: Four space-separated integers: M, N, M1, and M2

* Lines 2..M+1: Line i+1 describes row i of the pond using N
        space-separated integers with these values: 0 indicates empty
        water; 1 indicates a lilypad; 2 indicates a rock; 3 indicates
        the lilypad Bessie upon which she starts; 4 indicates the
        lilypad that is Bessie's destination.

SAMPLE INPUT (file bronlily.in):

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

INPUT DETAILS:

Bessie starts on the left in row 2; her destination is on the right in row
2. Several lilypads and rocks occupy the pond.

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of jumps between
        lilypads that Bessie must make to travel from her starting
        place to her destination.

SAMPLE OUTPUT (file bronlily.out):

2

OUTPUT DETAILS:

Bessie cleverly hops onto the pad at row 1, column 3 on her way to the
right hand side.

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

Problem 13: Buy One Get One Free [Jeffrey Wang, 2007]

Farmer John has discovered the Internet is buying bales of hay
online when he notices a special deal. For every bale of hay of
size A (1 <= A <= 1,000,000) he buys, he can get a bale of hay of
size B (1 <= B < A) for free!

The deal, however, is restricted: the larger bale must be high
quality hay and the smaller one must be low quality hay. FJ, being
a frugal and thrifty fellow, does not care: any quality of hay will
do as long as he saves some money.

Given a list of the sizes of N (1 <= N <= 10,000) bales of high
quality hay and M (1 <= M <= 10,000) bales of low quality hay, find
the maximum number of bales of hay Farmer John can purchase.  He
can buy bales of high quality hay without getting the free bale of
low quality hay, but he cannot buy bales of low quality hay (i.e.,
he must get them for free in the deal).

PROBLEM NAME: buyfree

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains a single integer which is the size
        of the ith bale of high quality hay.

* Lines N+2..N+M+1: Line i+N+1 contains a single integer which is the
        size of the ith bale of low quality hay.

SAMPLE INPUT (file buyfree.in):

3 4
6
1
3
1
5
3
4

INPUT DETAILS:

There are 3 bales of high quality hay, with sizes 6, 1, and 3, and 4 bales
of low quality hay, with sizes 1, 5, 3, and 4.

OUTPUT FORMAT:

* Line 1: The maximum total number of bales of hay Farmer John can
        obtain.

SAMPLE OUTPUT (file buyfree.out):

5

OUTPUT DETAILS:

Obviously, Farmer John can buy all the bales of high quality hay.
When he buys the size 6 high quality bale, he can get any low quality
bale for free (say, the bale of size 3). When he buys the size 3
high quality bale, he can get the size 1 low quality bale for free.
When he buys the size 1 high quality bale, however, he cannot get
any low quality bales for free (since the size must be strictly
less). The total, no matter how clever FJ is, comes to five bales.

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