Contest: FEB08 SILVER Division

ANALYSIS MODE
Submit solutions for your own enjoyment.

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

Problem 11: Dining Cows (Bronze) [Ionescu Victor and Brian Dean, 2007]

The cows are so very silly about their dinner partners. They have
organized themselves into two groups (conveniently numbered 1 and
2) that insist upon dining together in order, with group 1 at the
beginning of the line and group 2 at the end. The trouble starts
when they line up at the barn to enter the feeding area.

Each cow i carries with her a small card upon which is engraved D_i
(1 <= D_i <= 2) indicating her dining group membership. The entire
set of N (1 <= N <= 30,000) cows has lined up for dinner but it's
easy for anyone to see that they are not grouped by their dinner-partner
cards.

FJ's job is not so difficult.  He just walks down the line of cows
changing their dinner partner assignment by marking out the old
number and writing in a new one. By doing so, he creates groups of
cows like 112222 or 111122 where the cows' dining groups are sorted
in ascending order by their dinner cards. Rarely he might change
cards so that only one group of cows is left (e.g., 1111 or 222).

FJ is just as lazy as the next fellow. He's curious: what is the
absolute minimum number of cards he must change to create a proper
grouping of dining partners? He must only change card numbers and
must not rearrange the cows standing in line.

PROBLEM NAME: diningb

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 describes cow i's dining preference with a
        single integer: D_i

SAMPLE INPUT (file diningb.in):

7
2
1
1
1
2
2
1

INPUT DETAILS:

Seven cows; all but three of which currently prefer dining group 1.

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of cards Farmer
        John must change to assign the cows to eating groups as
        described.

SAMPLE OUTPUT (file diningb.out):

2

OUTPUT DETAILS:

Change the first and last cow's cards.

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

Problem 12: Long Distance Racing [Jeffrey Wang, 2008]

Bessie is training for her next race by running on a path that
includes hills so that she will be prepared for any terrain. She
has planned a straight path and wants to run as far as she can --
but she must be back to the farm within M seconds (1 <= M <=
10,000,000).

The entire path she has chosen is T units (1 <= T <= 100,000) in
length and consists of equal-length portions that are uphill, flat,
or downhill. The input data describes path segment i with a single
character S_i that is u, f, or d, indicating respectively uphill,
flat, or downhill.

Bessie takes U seconds (1 <= U <= 100) to run one unit of uphill
path, F (1 <= F <= 100) seconds for a unit of flat path, and D (1
<= D <= 100) seconds for a unit of downhill path.  Note that, when
returning home, uphill paths become downhill paths and downhill
paths become uphill paths.

Find the farthest distance Bessie can get from the farm and still
make it back in time.

PROBLEM NAME: racing

INPUT FORMAT:

* Line 1: Five space-separated integers: M, T, U, F, and D

* Lines 2..T+1: Line i+1 describes path segment i with a single
        letter: S_i

SAMPLE INPUT (file racing.in):

13 5 3 2 1
u
f
u
d
f

INPUT DETAILS:

Bessie has 13 seconds to get home (short workout!), and the total
path she has planned is 5 units long. She can run an uphill unit
in 3 seconds, a flat unit in 2 seconds, and a downhill unit in 1
seconds. The path looks like this:

 _/\_
/

OUTPUT FORMAT:

* Line 1: A single integer that is the farthest distance (number of
        units) that Bessie can get from the farm and make it back in
        time.

SAMPLE OUTPUT (file racing.out):

3

OUTPUT DETAILS:

She can run three units and back in 3 + 2 + 3 + 1 + 2 + 1 = 12
seconds, just a second less than her limit. If she tried to go
farther she would not make it.

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

Problem 13: Cow Multiplication [Jeffrey Wang, 2007]

Bessie is tired of multiplying pairs of numbers the usual way, so
she invented her own style of multiplication. In her style, A*B is
equal to the sum of all possible pairwise products between the
digits of A and B. For example, the product 123*45 is equal to 1*4
+ 1*5 + 2*4 + 2*5 + 3*4 + 3*5 = 54.  Given two integers A and B (1
<= A, B <= 1,000,000,000), determine A*B in Bessie's style of
multiplication.

PROBLEM NAME: cowmult

INPUT FORMAT:

* Line 1: Two space-separated integers: A and B.

SAMPLE INPUT (file cowmult.in):

123 45

INPUT DETAILS:

The two numbers are 123 and 45.

OUTPUT FORMAT:

* Line 1: A single line that is the A*B in Bessie's style of
        multiplication.

SAMPLE OUTPUT (file cowmult.out):

54

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