1993 USACO Qualifying Round

1. FRACTIONS TO DECIMALS

Write a program that will accept a fraction of the form N/D, where N is the numerator and D is the denominator, that prints out the decimal representation. If the decimal representation has a repeating sequence of digits, it should be indicated by enclosing it in brackets. For example, 1/3 = .33333333...is denoted as .(3), and 41/333 = .123123123...is denoted as .(123).

Typical conversions are:

1/3     =   .(3)
22/5    =  4.4
1/7     =   .(142857)
3/8     =   .375
45/56   =   .803(571428)

Test your program with the fractions above 
and the fraction 11/59.

Sample Run

ENTER N,D : 1,7

1/7 = .(142857)

2. PRIME CRYPTARITHM

The following cryptarithm is a multi- plication problem that can be solved by substituting digits from a specified set of N digits into the positions marked with *. If the set of prime digits {2,3,5,7} is selected, the cryptarithm is called a PRIME CRYPTARITHM.


      * * *
   x    * *
    -------
    * * * *
  * * * *
  ---------
  * * * * *

Write a program that will find all solutions to the cryptarithm above for any subset of digits from the set {1,2,3,4,5,6,7,8,9}.

Test your program with  the digits 23468 
and the prime digits 2357.

Sample Run
ENTER A SET OF DIGITS: 23468
      2 2 2
    x   2 2
     ------
      4 4 4     <3 more not shown>
    4 4 4
  ---------
    4 8 8 4

The number of unique solutions = 4

3. 6x6 CHECKER CHALLENGE

Examine the 6X6 checkerboard below and note that the six checkers are arranged on the board so that one and only one is placed in each row and each column, and there is never more than one in any diagonal. (Diagonals run from southeast to northwest and southwest to northeast and include all diagonals, not just the major two.)

          Column
    1   2   3   4   5   6
  -------------------------
1 |   | O |   |   |   |   |
  -------------------------
2 |   |   |   | O |   |   |
  -------------------------
3 |   |   |   |   |   | O |
  -------------------------
4 | O |   |   |   |   |   |
  -------------------------
5 |   |   | O |   |   |   |
  -------------------------
6 |   |   |   |   | O |   |
  -------------------------

The solution shown above is described by the sequence 2 4 6 1 3 5, which gives the column positions of the checkers for each row from 1 to 6.

ROW 1 2 3 4 5 6
COLUMN 2 4 6 1 3 5

This is one solution to the 6X6 Checker Challenge. Write a program that searches and finds all unique solution sequences to the 6x6 Checker Challenge. Print out the solutions using the column notation described above and count the total number of solutions found (including reflections and rotations.)

Sample Run

2 4 6 1 3 5
3 6 2 5 1 4
? ? ? ? ? ?
? ? ? ? ? ?

THERE ARE ? SOLUTIONS TO THE 
6X6 CHECKER CHALLENGE.

4. SHUTTLE PUZZLE

The SHUTTLE PUZZLE of size 3 consists of 3 white marbles, 3 black marbles, and a strip of wood with 7 holes. The marbles of the same color are placed in the holes at the opposite ends of the strip, leaving the center hole empty.

INITIAL STATE: WWW BBB

GOAL STATE: BBB WWW

To solve the shuttle puzzle use only two types of moves. Move 1 marble 1 space (into the empty hole) or jump 1 marble over 1 marble of the opposite color (into the empty hole). You may not back up, and you may not jump over 2 marbles.

A Shuttle Puzzle of size N consists of N white marbles and N black marbles and 2N+1 holes.

Write a program that will solve the SHUTTLE PUZZLE for any size N(*10) and display the board after each move. Use W to represent a white marble and B to represent a black marble and a blank to represent the empty hole. Test your program for N=3 and N=4.

Sample Run

N = 3

WWW BBB
WWWB BB
WW BWBB
W WBWBB
WBW WBB
WBWBW B
WBWBWB 
WBWB BW
WB BWBW
 BWBWBW
B WBWBW
BBW WBW
BBWBW W
BBWB WW
BB BWWW
BBB WWW

5. ALL LATIN SQUARES

A square arrangement of numbers

1  2  3  4  5
2  1  4  5  3
3  4  5  1  2
4  5  2  3  1
5  3  1  2  4

is a 5 x 5 Latin Square because each whole number from 1 to 5 appears once and only once in each row and column.

Write a program that will compute the number of NxN Latin Squares whose first row is:

1 2 3 4 5.......N

Your program should work for any N from 2 to 9.

Test your program for N=4 and N=5.

Sample Run

ENTER A WHOLE NUMBER (2-9): 4
THE NUMBER OF 4 x 4 LATIN 
SQUARES IS 24.

Answers

1. Fractions to Decimals
11/59 = .(18644067796610169491525423
72881355932203389830508474576271)

2. Prime Cryptarithm
      7 7 5
    x   3 3
     ------
    2 3 2 5
  2 3 2 5
  ---------
  2 5 5 7 5

    The number of unique solutions = 1

3. 6x6 Checker Challenge

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

There are 4 solutions to the 6x6 Checker 
Challenge.

4. Shuttle Puzzle
    n=4

wwww bbbb
wwwwb bbb
www bwbbb
ww wbwbbb
wwbw wbbb
wwbwbw bb
wwbwbwb b
wwbwb bwb
wwb bwbwb
w bwbwbwb
 wbwbwbwb
bw wbwbwb
bwbw wbwb
bwbwbw wb
bwbwbwbw
bwbwbwb w
bwbwb bww
bwb bwbww
b bwbwbww
bb wbwbww
bbbw wbww
bbbwbw ww
bbbwb www
bbb bwwww
bbbb wwww


5. All Latin Squares
  N=5
  The number of 5x5 Latin Squares is 1344.