Problems - 2001 Fall Open, Orange
PROBLEM 6: Word Diamonds [Don Piele, 2000]

A word diamond is formed from a word that begins and ends with the same letter. Consider this word diamond for the word `ENCODE':

     E
    N N
   C   C
  O     O
 D       D
E         E
 D       D
  O     O
   C   C
    N N
     E

The leftmost letter of the diamond just touches the left margin. A shorter diamond, e.g., for the word `DAD' looks like this:
  D
 A A
D   D
 A A
  D
      
Write a program that reads in a word and prints the word diamond associated with that word.

INPUT FORMAT:

A single line with a word that:
* Has all capital letters
* Has the same first and last letters
* Is between 3 and 13 letters in length

SAMPLE INPUT (file diamond.in):

DAD

OUTPUT FORMAT:

The word diamond itself. The word diamond for a word of length N has 2*N-1 lines. There are no spaces at the end of any line.

SAMPLE OUTPUT (file diamond.out):
  D
 A A
D   D
 A A
  D


PROBLEM 7: Factorial Power [Don Piele, 1983]

You probably already know that N factorial (shown as `N!') is the product of the integers from 1 through N:

12! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 = 479,001,600

The right-most non-zero digit in 12! is 6.

Write a program that reads an integer N (1 <= N <= 50,000,000) and calculates the rightmost non-zero digit.

Note that 10,000,000! has 2,499,999 zeroes on the end.

INPUT FORMAT:

A single integer, N

SAMPLE INPUT (file fact.in):

12

OUTPUT FORMAT:

A single line with an integer that is the rightmost non-zero digit of N!.

SAMPLE OUTPUT (file fact.out):

6


PROBLEM 8: Sum25 [Don Piele, 1982]

Write a program that inputs 7 digits (0 <= each digit <= 9) and counts the number of ways one can extract a set of digits to sum to 25. The digit `0' means 10, not 0.

This input:

5 0 1 5 4 3 7

yields five different sums to 25:

        5 0       3 7
        5   1 5 4 3 7
        5 0 1 5 4
          0 1   4 3 7
          0   5   3 7


INPUT FORMAT:

A single line with seven single digit integers.

SAMPLE INPUT (file sum25.in):

5 0 1 5 4 3 7

OUTPUT FORMAT:

A single line that tells the number of subsets that sum to 25.

SAMPLE OUTPUT (file sum25.out):

5
PROBLEM 9: Mother's Milk  [Traditional]

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

Write a program to help FJ determine how many liters of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

INPUT FORMAT:

A single line with the three integers A, B, and C.

SAMPLE INPUT (file milk.in):

8 9 10

OUTPUT FORMAT:

A single line that lists all the possible number of liters of milk that can be in bucket C when bucket A is empty. One space between numbers, please. No extra spaces on end of the line.

SAMPLE OUTPUT (file milk.out):

1 2 8 9 10
PROBLEM 10: Cows in Bed  [Hal Burch, 2001]

FJ has N (1 <= N <= 5000) cows who sleep in stalls in a barn with K stalls numbered 0..K-1. The i-th cow has a unique brand that is a number Si (1 <= Si <= 1,000,000). Each cow knows where to sleep because she sleeps in stall number Si mod K. Of course, cows will never want to share a stall for sleeping.

Given a set of cows and their brands, determine the minimum K such that no two cows sleep in the same stall.

INPUT FORMAT:

* Line 1: One integer: N

* Lines 2..N+1: One integer that is a cows brand

SAMPLE INPUT (file bed1.in):

5
4
6
9
10
13

OUTPUT FORMAT:

A single line with the minimum value of K on it. All legal input datasets can be solved within the allotted time.

SAMPLE OUTPUT (file bed1.out):

8