**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Four problems numbered 11 through 14
**********************************************************************

Problem 11: Cow Solitaire [Rob Kolstad, 2007]

Late summer on the farm is a slow time, very slow. Betsy has little
to do but play cow solitaire. For self-evident reasons, cow solitaire
is not so challenging as any number of solitaire games played by
humans.

Cow solitaire is played using an N x N (3 <= N <= 7) grid of ordinary
playing cards with four suits (Clubs, Diamonds, Hearts, and Spaces)
of 13 cards (Ace, 2, 3, 4, ..., 10, Jack, Queen, King). Cards are
named with two characters: their value (A, 2, 3, 4, ..., 9, T, J,
Q, K) followed by their suit (C, D, H, S). Below is a typical grid
when N = 4:

     8S AD 3C AC     (Eight of Spades, Ace of Diamonds, etc.)
     8C 4H QD QS
     5D 9H KC 7H
     TC QC AS 2D

To play this solitaire game, Betsy starts in the lower left corner
(TC) and proceeds using exactly 2*N-2 moves of 'right' or 'up' to
the upper right corner. Along the way, she accumulates points for
each card (Ace is worth 1 point, 2 is worth 2 points, ..., 9 is
worth 9 points, T is worth 10 points, J is 11, Q is 12, and K is
13) she traverses. Her goal is to amass the highest score.

If Betsy's path was TC-QC-AS-2C-7H-QS-AC, her score would be
10+12+1+2+7+12+1=45. Had she taken the left side then top
(TC-5D-8C-8S-AD-3C-AC), her score would be 10+5+8+8+1+3+1=36, not
as good as the other route. The best score for this grid is 69
points (TC-QC-9H-KC-QD-QS-AC => 10+12+9+13+12+12+1).

Betsy wants to know the best score she can achieve. One of the geek
cows once told her something about "working from the end back to
the beginning," but she didn't understand what they meant.

PROBLEM NAME: solitair

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 lists the cards on row i (row 1 is the top
        row) using N space-separated card names arranged in the
        obvious order.

SAMPLE INPUT (file solitair.in):

4
8S AD 3C AC
8C 4H QD QS
5D 9H KC 7H
TC QC AS 2D


OUTPUT FORMAT:

* Line 1: A single line with an integer that is the best possible
        score Betsy can achieve.

SAMPLE OUTPUT (file solitair.out):

69

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

Problem 12: The Flower Garden [Rob Kolstad, 2007]

Imagine Betsy's surprise as she rounded the barn and discovered
that Farmer John had built a secret greenhouse that was now brimming
with gorgeous flowers. Her mind ran wild as visions of a gorgeous
colorful garden swirled through her little bovine brain.

"I think I'll make a long row of F (7 <= F <= 10,000) flowers against
the far fence," she thought.  "I'll plant roses in every 3rd slot,
begonias in every 7th slot that is still open, and daisies in every
4th slot that is still open." Betsy wondered how many open slots
would remain. She realized that the number would depend on which
slot she started planting when she intended to fill every Nth slot
with a kind of flower.

Help Betsy know how many open slots will remain. Read a set of K
(1 <= K <= 100) planting descriptors, each of which tells a starting
location L (1 <= L <= F) -- L=1 is the first flower -- and an
interval I (1 <= I <= F) for planting flowers. Deduce the number
of empty slots that remain after planting the entire set.

If Betsy followed through on her initial vision, she might specify
the planting as:
      30 3     [30 slots total; 3 kinds of flowers]
      1 3      [start at slot 1 and plant roses every 3rd slot]
      3 7      [start at slot 3 and plant begonias every 7rd slot]
      1 4      [start at slot 1 and plant daisies in every 4th slot]

Thus, the empty garden looks like this:
     . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Then, after the rose planting:
     R . . R . . R . . R . . R . . R . . R . . R . . R . . R . .
Then, after the begonia planting:
     R . B R . . R . . R . . R . . R B . R . . R . B R . . R . .
Then, after the daisy planting:
     R . B R D . R . D R . . R . . R B . R . D R . B R . . R D .

13 empty slots remain after all the planting.

PROBLEM NAME: flowers

INPUT FORMAT:

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

* Lines 2..K+1: Line j contains two space-separated integers that
        specify the planting of one kind of flower: L_j and I_j

SAMPLE INPUT (file flowers.in):

30 3
1 3
3 7
1 4

INPUT DETAILS:

As in the problem's text

OUTPUT FORMAT:

* Line 1: A single line with a single integer that is the number of
        empty flower slots that remain after the planting is complete

SAMPLE OUTPUT (file flowers.out):

13

OUTPUT DETAILS:

As in the text

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

Problem 13: Cow Counting [Jeffrey Wang, 2007]

Farmer John wants to label his N (1 <= N <= 1,000,000) cows, but
cows don't like having the digit L (0 <= L <= 9) written on them,
so he avoids that.

If the cows are labeled with the smallest set of N positive integers
that don't have the digit L, what is the largest number that Farmer
John has to write on any cow?

PROBLEM NAME: count

INPUT FORMAT:

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

SAMPLE INPUT (file count.in):

10 1

INPUT DETAILS:

Farmer John has 10 cows he needs to label without using the digit 1.

OUTPUT FORMAT:

* Line 1: A single integer that is the largest number that Farmer John
        has to write on any cow.

SAMPLE OUTPUT (file count.out):

22

OUTPUT DETAILS:

The smallest 10 numbers he can use are: 2, 3, 4, 5, 6, 7, 8, 9, 20, and 22.

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

Problem 14: Bronze Cow Party [Richard Ho, 2006]

One cow from each of N farms (1 <= N <= 1000) conveniently numbered
1..N is attending the big cow party to be held at farm #X (1 <= X
<= N). Each of M (1 <= M <= 100,000) bidirectional roads connects
one farm to another. It is always possible to travel from one farm
to another on the roads. Traversing road i requires Ti (1 <= Ti
<= 100) units of time. One or more pairs of farms might be directly
connected by more than one road.

After all the cows gathered at farm #X, they realized that every
single cow left her party favors back at the farm. They decided to
suspend the party and send all the cows back to get the party favors.
The cows all travel optimal routes to their home farm and back to
the party. What is the minimum number of time units the party must
be suspended?

PROBLEM NAME: bparty

INPUT FORMAT:

* Line 1: Three space-separated integers, respectively: N, M, and X

* Lines 2..M+1: Line i+1 describes road i with three space-separated
        integers, respectively: Ai, Bi, and Ti. The described road
        connects Ai and Bi and requires Ti time units to traverse.

SAMPLE INPUT (file bparty.in):

4 8 2
1 2 7
1 3 8
1 4 4
2 1 3
2 3 1
3 1 2
3 4 6
4 2 2

INPUT DETAILS:

Four cows; eight roads; party at farm 2.

OUTPUT FORMAT:

* Line 1: One integer: the minimum amount of time the party must be
        suspended.

SAMPLE OUTPUT (file bparty.out):

6

OUTPUT DETAILS:

Direct paths connects farm 2 to each of the other farms (to farm
1: 7 and 3; to farm 3: 1; to farm 4: 2). The longest path is length
3, so the round-trip time is 6.

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