14th C. P. S. Competition Solutions









CROSSWORDS

The idea is simple, but the task is not. You are to design a program will generate solutions for crossword puzzles. The program will first accept words that must be placed horizontally (maximum 3) and words that must be placed vertically (maximum 3). The words must interlink in the same way that a crossword designer would place them. The spots where there are no letter must be filled this a star (*). Convert all letters to uppercase. These are the rules to calculate the penalty points for your solution.

INPUT

Up to 6 words, the first 3 to be placed horizontally, the next three being placed vertically.

OUTPUT

The program must display a rectangle representing the crossword puzzle. You must show at least 2 different solutions and the penalty associated with them. The lower the penalty for your best solution, the higher will your marks be compared to other competitors.
SAMPLE RUN

Crosswords



Enter horizontal word:  HELLO
Enter horizontal word:  loaf
Enter horizontal word:   (no word entered)
Enter vertical word: Elf
Enter vertical word: 
Enter vertical word: 

HELLO     Penalty (3 * 5 + 4 * 6 + 5 * 0) = 39
*LOAF     (LA, LA and OF were not entered)
*F***

HELLO     Penalty (3 * 5 + 4 * 0 + 5 * 4) = 35
*L***     (LOAF was not placed, 
*F***      but more than half the words interlinked)

**HELLO   Penalty (3 * 7 + 4 * 0 + 5 * 0) = 21
***L***   BEST SOLUTION
LOAF***

Again (y/n) N

DISK - O - TEC

You, and two friend, have been hired by a computer firm to clean up their office of all their unused diskettes. These are hidden in various desk drawers and must be collected together into a large pile. As a reward these diskettes are to divided up equally between you and your friends to take home. How many diskettes were there to start with if the following is true? (There is more than one answer to the puzzle.)

While eveybody was out at coffee, one of your friends sneeks into the room, divides up the diskettes into three equal piles, hides one of the piles and puts the others back into the original pile. There was one diskette left over after the division (ruined by a virus) which was thrown away.

At the next coffee break, the other friend came along, splits the new pile into 3 and hides his share. Again there was one left over (virus killed) which was thrown away. The others were piled back together.

At the end of the day, all the diskettes that were left in the pile were split up equally amongest you and your friends, and again there was one left over, killed by a virus.

INPUT

The judge will input a guess of how many diskettes there were in the original pile.

OUTPUT

The program must determine if that guess (or one of the next 10 numbers above it) satisfies the puzzle given above. If one of the numbers in the range satisfies the puzzle, print how many diskettes everybody gets to take home.
SAMPLE RUN

DISKOTEC



Number: 6
No valid number in the range 6 -- 16

Again (y/n): Y

Number: 48
Valid starting number: 52
Friend 1: 24       Friend 2: 18         Me:  7      Virus: 3

Again (y/n): N

EAT MORE

As you may know, they intend to upgrade the Saddle Dome so that the concessions are better run.

Suppose that there are 3 queues at the concessions:- one for hot dogs, one for soda and 1 for popcorn. Only one person can be served in each queue at a time. It takes 1 minute for each popcorn to be served, 2 minutes for each soda and 4 minutes for each hot-dog. The average person orders more sodas and popcorn than they do hot-dogs. The first thing to find out is how long it takes the average person to be served with the 3 queues we have now.

INPUT

The judges will enter the number of pop-corn, soda and hot dogs that 3 people want.

OUTPUT

The program must determine the average time it takes all the people to be served with the 3 queues given above. You should show the order for the people should queue for the food to minimize the total amount of time they spend in the queue. Rather than trying to work out a complicated algorithm to solve the problem, you are probably better off using a trial-and-error approach. Show at least 2 different solutions -- they do not have to be 'best'' solutions, only valid solutions.

SAMPLE RUNS

EAT MORE



First custumer (P/S/H): 2 1 0
Second customer (P/S/H): 2 2 1
Third customer (P/S/H): 1 1 1
            P       S        H
min 1       1       2        3     (Showing where each customer is
min 2       1       2        3      queuing and at what minute)
min 3       *       2        3     (Customer 1 has to wait for customer 2 )
min 4       *       2        3
min 5       3       1        2
min 6       *       1        2     (Customer 3 has to wait for customer 1)
min 7       *       3        2
min 8       *       3        2
min 9       2       *        *
min 10      2       *        *
Average = (6 + 8 + 10) = 8 mins

            P       S        H
min 1       1       2        3     (Showing where each customer is
min 2       1       2        3      queuing and at what minute)
min 3       2       1        3     (Customer 2 swaps with customer 1
min 4       2       1        3       so that customer 1 does not wait)
min 5       *       3        2     (Customer 2 swaps with customer  3
min 6       *       3        2       so that customer 3 does not wait)
min 7       3       *        2
min 8       *       *        2
min 9       *       2        *
min 10      *       2        *
Average = (4 + 7 + 10) = 7 mins (better)
Again (y/n): N

GOING DOWN IN FLAMES

A little known reason for the recent Flames hockey loss was the fact that the Canuks' defencemen introduced a computer virus into the lap-top computers that the Flames' forwards carried around their necks. This was how the program was supposed to work.

The ice was divided up into 7 rows and 7 columns ( 32 means that the puck is placed in the 3rd row 2nd column). A player passes the puck to the second player (the puck can only move along the columns and rows, not along a diagnol).

If the second player can pass back the puck to the first player, who can then pass back to the second player, who passes back to the first player WITHOUT THE PUCK CROSSING A PATH IT HAS MOVED IN ANY PREVIOUS PASSES, the Flames score a goal. If the path crosses, then that is where the Canuk player intercepts the puck and will go on and score a goal.

(Note: this programming technique is known in computer terms as ``ROUTING'' -- it is used in the design of boards and chips. ``ROUTING'' of a different kind is exactly what happened to the Flames)

INPUT

The judges will enter the positions of the two players. They will be valid positions and will not overlap.

OUTPUT

The program must determine whether the Flames or the Canuks score. If the Flames score, show the path of the puck. If the Canuks score, show where the puck was intercepted.
SAMPLE RUN

GOING DOWN IN FLAMES



First player: 22
Second player: 55
Flames score:	:-)  (Sideways Smiley)
*33333*
4X1113*
42**13*
42**13*
4222X3*
44444**
*******

Again (y/n): Y

First Player: 21
Second player: 56
Canuks score:   ;-(
3333333
X111113  Intercept at 52
2****13
2****13
22222X3
444444*
*******
Again (y/n): N
Wait till 1995 (or 1996 or 1997 or 1998)

This document last updated 1st January 1996 by M. Smith
(smith@enel.ucalgary.ca).