Usaco Jan10 Bronze

Part of USACO Jan10

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

Problem 11: DNA Sequencing [Jacob Steinhardt, 2010]

Farmer John is studying the geneology of his herd. He has M bulls
(1 <= M <= 20) and F cows (1 <= F <= 20). He doesn't know, though,
which bovines are potential descendants of which other bovines.

Farmer John does know the unique DNA sequence DNA_i of each and
every cow and bull on his farm. DNA_i has length 25 characters and
contains only upper-case letters 'A', 'C', 'G', and 'T'. He wants
to determine which bovines could possibly be children of which pairs
of cows and bulls.

Help Farmer John make this determination. For each pair of a cow
and a bull, print how many of FJ's other bovines could possibly be
their children. A bovine can be a child of a given cow and bull if

(1) it is not either of its parents (that is, a cow cannot be
its own mother and a bull cannot be its own father)
(2) each position in its DNA sequence matches at least one of
the characters in the same position in the two parent
sequences

So for example, 'abc' could come from pair ('axx', 'xbc'), but not
from the pair ('aaa', 'bbb').

Consider three bulls and two cows with these DNA sequences:

Bull 1: GTTTTTTTTTTTTTTTTTTTTTTTT
Bull 2: AATTTTTTTTTTTTTTTTTTTTTTT
Bull 3: GATTTTTTTTTTTTTTTTTTTTTTT
Cow 1:  TTTTTTTTTTTTTTTTTTTTTTTTT
Cow 2:  ATTTTTTTTTTTTTTTTTTTTTTTT

Bull 2 and cow 1 could be the parents of cow 2:
Bull 2: AATTTTTTTTTTTTTTTTTTTTTTT
Cow 1:  TTTTTTTTTTTTTTTTTTTTTTTTT
Cow 2:  ATTTTTTTTTTTTTTTTTTTTTTTT
since cow 2's first letter 'A' could be from Bull 2; cow 2's second
letter 'T' could come from cow 1; the remainder of the letters could
come from either parent.

Your goal is to create a matrix of the count of possible offspring
of each pairing of bulls and cows.

PROBLEM NAME: dna

INPUT FORMAT:

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

* Lines 2..M+1: Line i+1 gives the DNA sequence of bull i: DNA_i

* Lines M+2..M+F+1: Line j+M+1 gives the DNA sequence of cow j: DNA_j

SAMPLE INPUT (file dna.in):

2 3
TGAAAAAAAAAAAAAAAAAAAAAAA
AGAAAAAAAAAAAAAAAAAAAAAAA
ATAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAA
TTAAAAAAAAAAAAAAAAAAAAAAA

INPUT DETAILS:

Two bulls' DNA followed by three cows' DNA

OUTPUT FORMAT:

* Lines 1..M: Line i: F space-separated integers. The jth integer is
the number of bovines that could be children of the ith bull
and jth cow.

SAMPLE OUTPUT (file dna.out):

2 1 0
0 0 2

OUTPUT DETAILS:

Consider bull 1 and cow 1:

b1: TGAAAAAAAAAAAAAAAAAAAAAAA
c1: ATAAAAAAAAAAAAAAAAAAAAAAA

One might express the important part of their DNA as {T|A} followed
by {G|T}

Here's the 'matching' tests for bull 0 and cow 0:

b1: TGAAAAAAAAAAAAAAAAAAAAAAA -- parent, can't be offspring
b2: AGAAAAAAAAAAAAAAAAAAAAAAA offspring! Matches [TA][GT]
c1: ATAAAAAAAAAAAAAAAAAAAAAAA -- parent, can't be offspring
c2: AAAAAAAAAAAAAAAAAAAAAAAAA -- second character is 'A'; must be G or T
c3: TTAAAAAAAAAAAAAAAAAAAAAAA offspring! Matches [TA][GT]

Thus, the first element of the result matrix is 2. Other elements
derived similarly.

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

Problem 12: Theater Seating [Rob Kolstad, 2010]

The cows have built an amphitheater with seats in the form of a
rectangle with *odd* width W (11 <= W <= 101) and with R rows (4
<= R <= 50) of seats. The distance between two adjacent seats on
the same row is the same as the distance between a pair of seats
that are in front of/behind each other on adjacent rows.

The cows wish to sell tickets over the internet and have automatic
seating assignment for each ticket they sell.

Ticket purchasers always want the best seat, so every seat has a
unique 'priority' associated with it (even if some seats might
appear to the layman to have the same priority). The middle seat
of the first row (which is closest to the stage) is located at
1,(W+1)/2 and has the very best priority. The closest seats (euclidean
distance!) to it have the next set of best values. The next closest
seats have slightly worse values, and so on.

All seats of equal distance on the first row are better than all
seats of that same distance on the second row (and so on).

Since some seats are equidistant from the best seat, those on the
same row that are closest to seat number 1 (the left-most seat when
the seats are viewed from the stage) are given better priority (see
the diagram below).

Here's a diagram of a small (11 x 5) theater where the seat's
'priority' is shown with #1 being the best:

Seat Number
1  2  3  4  5  6  7  8  9 10 11
+----------------------------------
Row 5 | 54 50 44 38 32 29 33 39 45 51 55
Row 4 | 52 42 34 25 21 18 22 26 35 43 53
Row 3 | 48 36 23 14 12  9 13 15 24 37 49
Row 2 | 46 30 19 10  5  4  6 11 20 31 47
Row 1 | 40 27 16  7  2  1  3  8 17 28 41

Write a program that prints the seating priority chart for a supplied
width and row count.

PROBLEM NAME: tseat

INPUT FORMAT:

* Line 1: Two space-separated integers: W and R

SAMPLE INPUT (file tseat.in):

11 5

OUTPUT FORMAT:

* Lines 1..R: Line i contains W space-separated integers that are the
seating priorities for row R-i+1

SAMPLE OUTPUT (file tseat.out):

54 50 44 38 32 29 33 39 45 51 55
52 42 34 25 21 18 22 26 35 43 53
48 36 23 14 12 9 13 15 24 37 49
46 30 19 10 5 4 6 11 20 31 47
40 27 16 7 2 1 3 8 17 28 41

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

Problem 13: Word Morph [Jacob Steinhardt, 2010]

Farmer John is playing a word game against his cows. It
starts like this:
* Farmer John chooses a word, such as 'cat'
* The cows then choose their own word, perhaps 'dog'

Farmer John then must morph his word to the cows' word by performing
a number of steps, each one of which changes one single letter at
a time to make a new, valid word.

dict.txt. The file has no more than 25,000 words, each with length
in the range 1..20. These 'words' contain only letters in the range
'a'..'z'. The same dictionary is used for all tests.

For this example, Farmer John could make the following sequence of
four words:

'cat' -> 'cot' -> 'cog' -> 'dog'

to morph words from the first word 'cat' to the final word 'dog'
in just three moves. The cows will never give Farmer John an
impossible task. Farmer John must get from his word to the cows'
word in as few moves as possible.

You will be given a starting word and an ending word.  Determine
and output a number which is the least number of legal letter changes
required to morph the starting word to the ending word.

PROBLEM NAME: wmorph

INPUT FORMAT:

* Line 1: A single string that is the starting word

* Line 2: A single string that is the end word

SAMPLE INPUT (file wmorph.in):

cat
dog

OUTPUT FORMAT:

* Line 1: A single integer that is the number of times a letter must
be changed to transform the starting word into the ending
word.

SAMPLE OUTPUT (file wmorph.out):

3

**********************************************************************```
```
page revision: 0, last edited: 15 Jan 2010 02:22