Problems - 1998 Spring Open
PROBLEM 1: Different Dice [Hal Burch]
In a different galaxy far far away there are different kinds of dice, often with unusual integer numbers of sides. These dice can have anywhere from 2 to 16 (integer) sides. Each side can have from 1 to 32 (integer) spots. Sets of dice contain anywhere from 1 through 32 dice.

These dice roll just like Earth-based dice, of course: the outcome of rolling is considered to be the sum of the spots showing on each die. Anthropologists digging through old ruins in the galaxy far far away have found sets of dice that have various different numbers of spots. Here's one set of two two-sided dice they found:

{2,3} and {3,4}
and here's another:
{1,2} and {4,5}
It's easy to see that the first set of dice yields sums of 5, 6, and 7. The second set also yields 5, 6, and 7. Furthermore, the probability of rolling a five is 1/4, rolling a six is 1/2, and rolling a a seven is 1/4 for both sets of dice.
Given two sets of dice, your program must decide if they yield the same sets of sums. Additionally, it must also decide if the two sets yield those sums with the same probabilities.

INPUT FORMAT:

The first line of the input file contains two space-separated integers D1 and S1. D1 is the number of dice in the first set, and S1 is the number of sides on each die.

The subsequent D1 lines each contain S1 values that specify the spot values for a die. The values might or might not all be different. The next line of the input file contains two space-separated integers D2 and S2. D2 is the number of dice in the second set, and S2 is the number of sides on each die.

The subsequent D2 lines each contain S2 values that specify the spot values for a die. The values might or might not all be different.

OUTPUT FORMAT:

The first line of the output file contains a `Y' or `N'. `Y' indicates that both sets of dice yield the same set of possible sums. `N' indicates otherwise.

The second line of the output file contains a `Y' or `N'. `Y' indicates that both sets of dice yield the same set of possible sums with the same set of probabilities of achieving those sums. `N' indicates otherwise.

The third line of output contains two, space-separated integers. The first integer indicates the number of possible sums the first set of dice could yield. The second integer indicates the number of different sums the second set of dice could yield.

SAMPLE INPUT (file INPUT.TXT):

2 6 1 2 3 4 5 6
1 2 4 3 4 1
3 4
1 4 3 2
5 3 2 1
1 1 1 1
SAMPLE OUTPUT (file OUTPUT.TXT):

N
N
9 8
[Problem|Data|Solutions]

PROBLEM 2: Feed Ratios [Similar to ACM Finals, 1998, forwarded by Dan Adkins]
Farmer John feeds his cows only the finest mixture of cow food, which has three components: Barley, Oats, and Wheat. While he knows the precise mixture of these easily mixable grains, he can not buy that mixture! He buys three other mixtures of the three grains and then combines them to form the perfect mixture.

Given a set of integer ratios barley:oats:wheat, find a way to combine them IN INTEGER MULTIPLES to form a mix with some goal ratio x:y:z.

For example, given the goal:

        3:4:5
and the ratios of three mixtures:
        1:2:3
        3:7:1
        2:1:2
Your program should find some minimum number of integer units (the `mixture') of the first, second, and third mixture that should be mixed together to achieve the goal ratio or print `NONE'. `Minimum number' means the sum of the three non-negative mixture integers is minimized.

For this example, you can combine eight units of mixture 1, two units of mixture 2, and five units of mixture 3 to get seven units of the goal ratio:

    8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) = (21:28:35) = 7*(3:4:5)
Integers in the goal ratio and mixture ratios are all non-negative and smaller than 100 in magnitude.

INPUT FORMAT:

The first line of the input file contains three space separated integers that represent the value of the goal ratios.

The next three lines of the input file each contain three space separated integers that represent the ratios of the three mixtures purchased.

OUTPUT FORMAT:

The output file should contain one line containing four integers or the word `NONE'. The first three integers should represent the number of units of each mixture to use to obtain the goal ratio. The fourth number should be the multiple of the goal ratio obtained by mixing the initial feed using the first three integers as mixing ratios.

SAMPLE INPUT (file INPUT.TXT):

3 4 5
1 2 3
3 7 1
2 1 2
SAMPLE OUTPUT (file OUTPUT.TXT):

8 1 5 7
[Problem|Data|Solutions]

PROBLEM 3: The Tamworth Two [Richard Forster, BOI]
A pair of cows is loose somewhere in the forest. Farmer John is lending his expertise to their capture. Your task is to model their behavior.

The chase takes place on a 10 by 10 planar grid. Squares can be empty or they can contain: an obstacle, the cows (who always travel together), or Farmer John. The cows and Farmer John can occupy the same square (when they `meet') but neither the cows nor Farmer John can share a square with an obstacle.

Each square is represented as follows:

. Empty square
* Obstacle
C Cows
F Farmer
Here is a sample grid:
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
The cows wander around the grid in a fixed way. Each minute, they either move forward or rotate. Normally, they move one square in the direction they are facing. If there is an obstacle in the way or they would leave the board by walking `forward', then they spend the entire minute rotating 90 degrees clockwise.

Farmer John, wise in the ways of cows, moves in exactly the same way.

The farmer and the cows can be considered to move simultaneously during each minute. If the farmer and the cows pass each other while moving, they are not considered to have met. The chase ends when Farmer John and the cows occupy the same square at the end of a minute.

Read a ten-line grid from INPUT.TXT that represents the initial state of the cows, Farmer John, and obstacles. Each of the ten lines contains exactly ten characters using the coding above. There is guaranteed to be only one farmer and one pair of cows. The cows and Farmer John will not initially be on the same square.

Calculate the number of minutes until the cows and Farmer John meet. Assume both the cows and farmer begin the simulation facing in the `up' direction. Print 0 if they will never meet.

INPUT FORMAT:

The input file contains ten lines of ten characters (no spaces).

OUTPUT FORMAT:

The output file should contain one line containing a single integer that represents the numbers of minutes until Farmer John and the Cows meet. Print 0 if they never meet.

SAMPLE INPUT (file INPUT.TXT):

*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
SAMPLE OUTPUT (file OUTPUT.TXT):

49
[Problem|Data|Solutions]

PROBLEM 4: Subset Sums [Recreational Mathematics Newsletter, Kolstad]
For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical.

For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical:

{3} and {1,2}
This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions).

If N=7, there are 4 ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum:

{1,6,7} and {2,3,4,5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.

Your program must calculate the answer, not look it up from a table.

INPUT FORMAT:

The input file contains a single line with a single integer representing N, as above.

OUTPUT FORMAT:

The output file contains a single line with a single integer that tells how many same-sum partitions can be made from the set {1, 2, ..., N}. The output file should contain 0 if there are no ways to make a same-sum partition.

SAMPLE INPUT (file INPUT.TXT):

7
SAMPLE OUTPUT (file OUTPUT.TXT):

4
[Problem|Data|Solutions]

PROBLEM 5: Stringsobits [Kim Schrijvers]
Consider an ordered set S of strings of N (1 <= N <= 32) bits. Bits, of course, are either 0 or 1.

This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.

Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set.

INPUT FORMAT:

The input file contains a single line with three space-separated integers, N, L, and I.

OUTPUT FORMAT:

The output file should contain a single line with a single integer that represents the Ith element of the set of integers of length N bits with no more than L bits that are `1'.

SAMPLE INPUT (file INPUT.TXT):

5 3 19
SAMPLE OUTPUT (file OUTPUT.TXT):

10011
[Problem|Data|Solutions]