1993 (Niagara South)

Third Annual Niagara South Board

Programming CONTEST

March 1993

DO NOT TURN THIS PAGE UNTIL YOU ARE INSTRUCTED‑TO DO SO AND HAVE READ THE FOLLOWING CAREFULLY

1. YOU WILL HAVE TWO AND ONE‑HALF HOURS FOR THIS CONTEST.

2. ALL SOLUTIONS ARE TO BE STORED ONTO THE DISKETTE GIVEN TO YOU BY THE PRESIDING TEACHER.

3. PRINTING IS NOT ALLOWED DURING THE CONTEST.

4. SOLUTIONS WILL BE JUDGED ON THE BASIS OF LOGICAL CORRECTNESS AND ALSO GOOD STRUCTURED STYLE, INPUT VALIDATION, AND SCREEN PRESENTATION.

5. YOU ARE TO ATTEMPT ONLY 2 QUESTIONS FROM PART A, I QUESTION ONLY FROM PART B AND 1 QUESTION ONLY FROM PART C.

6. IN DETERMINING YOUR OVERALL SCORE, THE 2 QUESTIONS FROM PART A ARE WORTH 25 POINTS EACH, THE 1 QUESTION FROM PART B IS WORTH 50 POINTS AND THE I QUESTION FROM PART C, 75 POINTS.

7. BY SUBMITTING ANY SOLUTION(S) TO ANY PROBLEM(S) IN THIS CONTEST YOU WILL HAVE GIVEN CONSENT TO THE NIAGARA SOUTH PROGRAMMING COMMITTEE TO USE YOUR SOLUTION IN ANY WAY.

1993 NSPC GUIDELINES

The Computer Studies Council felt it was not necessary to have a formal review of the dates and procedures used in the administration of the 1993 Niagara South Programming Contest. A brief discussion of the guidelines at the regular February meeting of the Council indicated that minor changes should be made in items 1, 2, The recommendations follow:

1. That the final form of the NSPC be ready for distribution to the Council representatives from each participating school at the Council meeting on Tuesday, March 2, 1993.

2. That the contest be held on Thursday, March 4, 1993 in each of the participating schools. For this year, only Niagara South schools will be participating.

3. That the solutions to the problems be given in one of the following programming languages: WATCOM BASIC, WATCOM PASCAL, TURING, Qbasic.

4. That in assembling the final contest, the committee will place questions into three parts. "A", "B" and "C" corresponding to the levels of difficulty referred to above. Students must complete 2 questions from Part A, 1 from Part B, and 1 from Part C. The contest will have a time limit of 2 1/2 hours. All solutions are to be submitted on diskette; no printing will be allowed during the contest itself.

5. That each participating school make sure the computer lab is ready and available for use on the day of the contest and supply diskettes for use by the participants and that completed work is collected, sent to the marking committee (see item 6 below) by 3:30 p.m. of the next day ( or other time agreed to at the Council Meeting on March 2, 1993 ).

6. That each participating school field a team consisting of at most 8 students. The team should have at most:

‑ 3 students enrolled in their 4th or 5th secondary school year

‑ 3 students enrolled in their 3rd secondary school year

‑ 3 students enrolled in their 1st or 2nd secondary school year

That the names and year of each of the contestants should be submitted on letter accompanying the solutions diskette(s).

That a $2.00 per contestant fee be brought to the March meeting of the Computer Studies Council. These funds will be used to pay for the entry fee to the ECOO Competition.

PART A

DO 2 QUESTIONS FROM THIS PART

QUESTION A‑1 [SAVE ON DISK AS "QA.1"]

Different categories for taxable income call for different calculation of tax payment. Several of the categories of upper taxable incomes and their rates are as follows:

Taxable Income Tax Calculation

up to $10,000 12% of taxable Income

up t $15,000 $1200 + 18% of amount over $10,000

up to $20,000 $2100 + 25% of amount over $15,000

up to $30,000 $3350 + 30% of amount over $20,000

over $30 000 $6350 + 35 % of amount over $30,000

Write a program which accepts a person' s taxable income as input and outputs the amount of income tax that should be payed.

QUESTION A‑2 [SAVE ON DISK AS "QA.2"]

A Triangular Number can be represented as a triangle of dots or 0's. The following examples illustrate the first four triangular numbers

1: 0 3: 0 6: 0 10: 0

00 00 00

000 000

0000

In each case, the triangular number is the total number of 0's in the triangle. You are asked to write a program which accepts any positive number, and determines if it is triangular or not. If it is, then print the triangle as in the examples above. If it is not, report that it is NOT Triangular.

QUESTION A‑3 [SAVE ON DISK AS "QA.3" ]

Write a program which accepts an unknown number of positive numbers as input. Input should be terminated by entering ANY non‑positive value. The output should be the third largest number entered. The data may NOT be stored in an array, the program must NOT sort the entire set of data and the data may only be entered one time.

QUESTION A‑4 [SAVE ON DISK AS "QA.4" ]

A FIBONACCI sequence is a sequence of numbers generated by starting with two integers t₁ and t₂. Successive terms are determined by adding the most recent two terms together.

ie: tn = t_n-2 + t_n-l for n=3, 4, 5, ...

eg: Given t_l =1 and t₂ =1, the sequence generated should be

1, 1, 2, 3, 5, 8, 13, 21, ...

Write a program which accepts three numbers as input. The first two numbers will represent the first two numbers of the sequence. The third will represent to how many terms the fibonacci sequence should be generated. The output should be the last fibonacci number generated.

SAMPLE INPUT: 1, 1, 6

EXPECTED OUTPUT: 8 (see sequence above)

PART B

DO ONLY 1 QUESTION FROM THIS PART

QUESTION B‑1 [SAVE ON DISK AS "QB.1" ]

FRACTION CALCULATOR: Your program will accept 4 integers and one of the following operators: " *", " + ", "‑", "/" . The four digits entered will be placed in variables a, b, c and d which will form the fractions a/b and c/d. The output should be a well formatted representation of the question, and the fully reduced result of the input operation performed on the two fractions.

SAMPLE INPUT: 1,2,3,4, +

SAMPLE OUTPUT: 1 3 1

--- + --- = 1 ---

2 4 4

SAMPLE INPUT: 1,3,3,4, *

SAMPLE OUTPUT: 1 3 1

--- * --- = ---

3 4 4

QUESTION B‑2 [SAVE ON DISK AS "QB.2" ]

Write a program which accepts any number of non‑zero integers terminating with the sentinel 0. Determine the largest sum of any sublist entered. Output this largest sum and the starting and end points of the sublist.

SAMPLE INPUT: ‑2, 6, 11, ‑1, 15, 3, ‑8, 0

SAMPLE OUTPUT: The largest sum is 34 and is found by using the sublist of elements 2 through 6.

QUESTION B‑3 [SAVE ON DISK AS "QB.3" ]

The LCM (lowest common multiple) of two non‑zero integers can be found using the formula:

lcm(u, v) = u*v/ gcd(u, v) where: gcd(u,v) is the greatest common divisor of u and v.

Write a program which takes any two non‑zero integers as input and outputs the lowest common multiple of the numbers. The method used in the solution MUST use the method described above.

PART C

DO ONLY 1 QUESTION FROM THIS PART

QUESTION C‑1 [SAVE ON DISK AS "QC.1" ]

Pattern Matching: Write a program which accepts two sets of data. The first set of data will be a list of 5 unique strings, each a maximum of 11 characters in length. The second set of data will be ONE string to match against the first set of data. The items in the second set MAY contain wild card characters. Wild cards are defined as:

'?' ‑ matches ANY single character

'*' ‑ matches 0 or more characters

For example, the pattern "*.bas" will match all strings ending in ".bas". The pattern "prog.???" will match any string starting with "prog." and ending in any THREE additional characters.

If the pattern given in the second data set matches any strings in the first set, your program should report the matches found, otherwise, report that there were no matches.

SAMPLE INPUT: DATA SET #1 ‑ HINTS, TELLX, FATS, BILLS, DOTS, FRED, PILLOW

DATA SET #2 ‑ *LL?

QUESTION C‑2 [SAVE ON DISK AS "QC.2" ]

Write a program which accepts three words as input. The first two words are expected to be three characters in length. The third word may be either three or four characters in length. The words entered will form a puzzle to solve. If the words CAT, DOG and RATS were entered, the resulting puzzle would be:

CAT

+DOG

____

RATS

To solve the puzzle, your program must find unique digits 0 ‑ 9 to replace each of the letters with so that the given sum is correct. No digit may be used for more than one letter. All occurrences of the same letter must be replaced by the same digit. The output should be the original puzzle and the solution IF THERE IS ONE. The output from the above example would be

CAT 806

+DOG 257

____ ____

RATS 1063

QUESTION C‑3 [SAVE ON DISK AS "QC.3" ]

THE Game of LIFE: In this question you will be simulating the game of LIFE as invented and described by John H. Conway. This simulation is intended to model the genetic laws of birth, survival and death. This simulation will be 'played' on a board which is 20 squares in the horizontal direction and 15 squares in the vertical direction. Each square can be empty or can contain an X indicating the presence of an organism in that square. Each square (except the border squares) has eight neighbours.

The next generation of organisms is determined according to the following criteria:

Write a program which accepts exactly 10 pairs of co‑ordinates indicating the positions of ten organisms living on the board. The co‑ordinates should represent the horizontal and vertical positions, with the bottom left square called position 1, 1 and the top right position called 20, 15. Print a copy of the original configuration to the screen. Calculate 5 new generations of life, printing each new generation on the screen. The final generation should be left on the screen.