USACO Final Round 1

The problems used in the first annual USA Computing Olympiad. 
Each student 
Problem 1:  Ordered Fractions

PROBLEM STATEMENT:

Consider the set of all reduced rational numbers between 0 and 1 
inclusive with denominators less than or equal to N.

Here is the set when N = 5:

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

Write a program that, given an integer N between 1 and 100 inclusive, 
prints the fractions in order of increasing magnitude. You should also 
print the total number of fractions. Print a tab after each fraction so 
they don't run too far off the screen during judging.

TECHNICAL CONSTRAINTS:

1. Put your solution in an ASCII text file named FRACiiss.xxx, where
	o The extension .xxx is:
		-  PAS for PASCAL programs
		-  C for C programs
	o The string iiss identifies you, where ii should be your 
initials, and ss should 
		be your state abbreviation (i.e. FRACNBNC.C for 
Nate Bronson from 
		North Carolina)

2. Programs must reject inputs where N is less than 1 or greater than 
100.

SAMPLE RUN:

Enter the maximum denominator: 5
0/1  1/5  1/4  1/3  2/5  1/2  3/5  2/3  3/4  4/5  1/1
There were 11 fractions.


Problem 2: Biggest Barn

A farmer wants to build a barn on his farm, and he wants it to cover as 
much area as possible. But his farm has trees and other buildings on it, 
and he does not want to move anything. For simplicity, the farm is 
represented as an m by n grid, with trees and buildings occupying one 
or more of the grid locations. The rectangular barn must not touch 
anything else. If the farm is the following 5 by 6 grid,

      1 2 3 4 5 6
    1 XX
    2
    3
    4     XXXX
    5     XXXX

then the barn might be

      1 2 3 4 5 6
    1 XX  BBBBBBBB
    2     BBBBBBBB
    3
    4     XXXX
    5     XXXX

or

      1 2 3 4 5 6
    1 XX
    2
    3 BB
    4 BB  XXXX
    5 BB  XXXX

In this case the largest barn runs from 1,3 to 2,6, with area 8.

The PROBLEM is to determine the size (area) of the biggest barn and 
the total number of possible locations for all the barns of that size. 

PROBLEM STATEMENT:

1. Read from the data file BARN.IN any number of data sets. The data 
file will begin with a line containing the number of obstacles in the 
next data set. The next line will contain the height and the width of 
the farm. The following lines will contain the row, column, height, 
and width of each obstacle. The data sets will be terminated with a line 
containing a negative number. There will be at least one data set, and 
each data set will have at least one obstacle. A data file for the 
example above would be:

      2
      5 6
      1 1 1 1
      4 3 2 2
      -1

2. Find the size of the largest barn and the number of different barns of 
maximum size that can be built. Output them in the form:

      Maximum area = ###, number of solutions = ###.



For part 2, the width and height of the total grid will be less than or 
equal to 20.  The total number of rectangles in the input data will be 
less than or equal to 20.

Note: A program that meets the requirements for PART 3 
automatically meets the requirements for PART 2.

3. The width and height of the total grid may be anything less than 
1,000. All other specifications are the same as for PART 2. Remember 
that 1,0002 > 216.

TECHNICAL CONSTRAINTS:

1. Put your solution in an ASCII text file named BARNiiss.xxx, where
	o The extension .xxx is:
		-  PAS for PASCAL programs
		-  C for C programs
	o The string iiss identifies you, where ii should be your 
initials, and ss should 
		be your state abbreviation (i.e. BARNNBNC.C for 
Nate Bronson from 
		North Carolina)

TEST DATA WITH SOLUTIONS:

   BARN.IN:
      2
      5 6
      4 3 2 2
      1 1 1 1
      2
      11 13
      1 1 5 5
      7 9 5 5
      -1
   
   output:
      Maximum area = 8, number of solutions = 1.
      Maximum area = 35, number of solutions = 2.


Problem 3: Polyominoes

A ``polyomino’’ is a two dimensional figure formed from N squares 
with adjoining sides. Here is the set of polyominoes for N=4:

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

Note that some of the five polyominoes might appear in other 
orientations if they are reflected or rotated.  Consider these alternate 
presentations of the fourth one above:

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

PROBLEM STATEMENT:

Write a program which will create and print the polyominoes of order 
N. It should print each polyomino only once (i.e., in just one of its 
orientations). Order of the listing is unimportant. You should also 
display the number of distinct polyominoes.

The judges will award extra credit for programs that can compute 
polyominoes of order 9 or above (using no more than 60 seconds of 
CPU time on one of the 486/33 machines).  Programs vying for extra 
credit should include an option (indicated by a negative value for N) 
that prints only the number of polyominoes found and doesn't print out 
the polyominoes themselves.

TECHNICAL CONSTRAINTS:

1. Put your solution in an ASCII text file named POLYiiss.xxx, where
	o The extension .xxx is:
		-  PAS for PASCAL programs
		-  C for C programs
	o The string iiss identifies you, where ii should be your 
initials, and ss should 
		be your state abbreviation (i.e. POLYNBNC.C for 
Nate Bronson from 
		North Carolina)

SAMPLE RUNS:

Enter N: 4
 ****

 *
 ***

  *
 ***

  **
 **

 **
 **					

There were 5 polyominoes.

(Extra Credit Runs)
Enter N: -4
There were 5 polyominoes.

Problem 4: Word Morphing

In this problem you will transform words into other words, one 
character at a time. 

PROBLEM STATEMENT:

1. 1-morphs: The set of 1-morphs of a word is the set of words in 
which one letter is changed and no letters are rearranged. Write a 
program which prints a list of all the 1-morphs of a word. You will be 
provided with a dictionary file named WORDS of acceptable words in 
alphabetical order, one word to a line.

2. Laddergrams: A laddergram is a chain of 1-morphs which 
transforms a starting word into an ending word. For example, the 
shortest laddergram changing the word "lead" into the word "gold" is 
lead load goad gold. Write a program which finds and prints a 
laddergram of shortest length between the supplied starting and 
ending words (using the same supplied dictionary). 

3. All solutions: Note that we wrote "a laddergram of shortest length" 
in 2 above, not "the laddergram of shortest length". A particular 
change-the-word problem may actually have several shortest solutions. 
Write a program which finds and prints all the shortest solutions.

4. Widest chains: Find the length of the longest optimal laddergram 
for words of length 5 in the supplied dictionary. You do not have to 
write a particular program to compute the result, but there must be a 
basis for your conclusion.

TECHNICAL CONSTRAINTS:

1. Put your solution in an ASCII text file named WORDiiss.xxx, 
where
	o The extension .xxx is:
		-  PAS for PASCAL programs
		-  C for C programs
	o The string iiss identifies you, where ii should be your 
initials, and ss should 
		be your state abbreviation (i.e., WORDNBNC.C for 
Nate Bronson from 
		North Carolina)

SAMPLE RUNS:

Part 1: 

The 1-morphs of TIMES are: 
   timer timed tires tiles tides tames limes dimes

Part 2:

Here are some shortest solutions you can use to test your program:

LOVE to HATE: love lone lane late hate
BRAIN to THINK: brain train trait tract track trick thick think
WHITE to BLACK: white whine shine spine spice slice slick slack 
black