Preliminary Round

This page contains links to all of the material needed to complete the Preliminary Round of the UNSW High Schools Programming Competition.

The detailed rules of the competition are given at:netscape & http://do.cse.unsw.edu.au/progcomp/rules.html. Please read the rules carefully before commencing the competition.

In order to permit a wide range of languages to be used there are no strict requirements on the method of entering the test data or the method of displaying the results. You may supply your programs with the data in whichever way you wish.

Run each program on the test data provided. Print out the results of each run and submit these with the program listings.

The supervisor must sign the cover sheet and submit this together with all your printouts by express post mail. If possible please also submit an electronic copy to progcomp@cse.unsw.edu.au immediately after the competition. If you do not have access to email at your school the printed copy will be sufficient. Electronically submitted solutions will be marked more quickly.

Marks will be awarded for correct behaviour and for programming style. Good style involves simple clear programs with brief but informative comments.

Tasks may be completed in any order. You must stop working and submit your work so far after 2 hours. You can submit program listings, even if they're not working.

Good Luck!

Task 1 - Anagram

Description

An anagram is a word or phrase obtained by rearranging the letters of another word or phrase.

For example Neo is an anagram of One. And Tom Marvolo Riddle is an anagram of I am Lord Voldemort

Write a program which, given two strings string1 and string2, prints:


"string1" is an anagram of "string2"

if they are anagrams, and


"string1" is NOT an anagram of "string2"

otherwise.

Test Data

String 1	String 2
One	Neo
Eat, Fish	A he fist!
Howard!	Sorry?
Tom Marvolo Riddle	I am Lord Voldemort
Sheep eat feed	eeeee Shp at fd
Sheep eat feed	eeee Shp at fd

Sample Output


"One" is an anagram of "Neo"

"Eat, Fish" is an anagram of "A he fist!"

"Howard!" is NOT an anagram of "Sorry?"

Constraints

Ignore punctuation, digits, and all other non-letters. Ignore the case of letters (as in the examples above). You may assume each string is no longer than 80 characters.

Task 2 - Factor Pairs

Description

A factor pair of a whole number is a pair of whole numbers which equal the initial number when multiplied together. All numbers have a factor pair which is one and themself (eg 7 = 7 * 1) - we call this the trivial factor pair.

Write a program which, given a whole number, prints a factor pair for it. Only print the trivial factor pair if there are no other factor pairs. If the number has more than one non-trivial factor pair you may print whichever you wish.

The format of your output is to match the examples below. Print the smaller of the numbers in the factor pair first, then the larger one.

Test Data

Find factor pairs for the numbers below:

100

561

17947

25849

197203

Sample Output


7 = 1 * 7

144 = 6 * 24

Constraints

You may assume each input is a whole number greater than 1 and less than 64000.

Task 3 - Seventeen

Description

Write a program which, given a list of numbers returns all ways of combining some or all of the numbers using plus and minus to produce 17.

For example 1,3,3,7,9 can be combined as follows


17 = 1 + 7 + 9 

17 = 1 + 3 - 3 + 7 + 9 

17 = 1 - 3 + 3 + 7 + 9

Only consider cases where the numbers are in the same order they appear in the input list. (eg "17 = 7 + 9 + 1" would not be valid in the example above).

You may not use a number more times than it appears in the input list. (e.g. in the example above 3 can be used zero, one or two times, and the other numbers can only be used at most once).

Test Data

1,3,3,7,9

1,1,1,1

17,14,3

17,14,3,13,4

1,3,5,7,9,11,13,2

Output

If there is no way of combining the input numbers to produce 17 print "No solution possible". Otherwise match the format of the output given in the example above.

Where there is more than one way of combining the numbers to produce 17 you may return them in whichever order you wish.

Constraints

You may assume the input is at most 20 numbers. You may assume all the input numbers are whole numbers and are not negative.

Task 4 - Buckets

Description

If you had a 3 litre bucket called A, and a 5 litre bucket called B, and a water tap, you could measure 4 litres with the following procedure:


fill B from the tap

tip 3 into A

empty A

tip 2 into A 

fill B from the tap

tip 1 into A

Done!

Write a program which, given the size of A, the size of B, and the desired amount to measure, returns a series of lines describing how to measure it.

Test Data

Size of A (litres)	Size of B (litres)	Amount to measure
3	5	4
3	5	2
11	5	3
10	5	3

Output

If there is no way of producing the desired amount print "No solution possible". Otherwise match the format of the output in the example above.

Hint: You may assume that if there is a solution it can be obtained by repreatedly pouring one container into the other.

Task 5 - Round Robin

Description

n teams are to play each other in a competition. In each round each team plays exactly one other team. We wish to have as few rounds as possible.

Write a program which, given an even number n, produces a "draw table" showing which team plays which team in each round. It is to take the minimum possible number of rounds. If more than one such draw table is possible your program may return whichever you wish.

For example here is an 4 player draw table

The letters represent the four teams, the numbers say which round each pair of teams is playing.

Test Data

Number of teams
4
6
8
10

Output

Match the format of the output in the example above.

Where there is more than one "draw table" you may return whichever you wish.

Constraints

You may assume the input is even.

Task 6 - Pig

Description

You wish to alter the words in a sentence. You use the following procedure: If the word starts with a vowel add the letters "tay" to the end of the word. Otherwise move the first letter of the word to the end of the word, and then add "ay" to the end of this new word.

Write a program which, given a string of words, alters each word in accordance with the above procedure. Assume each "word" starts and finishes with a space character or is at the start or the end of the string.

Example

Here is an example of an altered sentance:


  I like nix aeroplane Jelly

becomes


  Itay ikelay ixnay, aeroplanetay Ellyjay.

Test Data

Phrase to encode
I like nix aeroplane jelly
You have to see it for yourself
Are you ready
Read my lips

Output

Match the format of the output in the example above. Ignore punctuation. If a word starts with a capital letter in the input phrase, then the corresponding word in the output phrase must also. If the first letter of the original word is uppercase convert it to lowercase when you move it UNLESS every letter in the original word is uppercase.

Constraints

You may assume the input is less than 80 characters long.

- cut - here -

The University of New South Wales
School of Computer Science and Engineering
UNSW High Schools Programming Competition 2000

Preliminary Round Submission Cover Sheet

This form must accompany the program listings and test runs produced by the team identified below, and must be signed by the supervisor. Please remember to submit one form for each team.

Name of School:

Name of Team:

Team Members:
(Family names only)

Session Details:

Date:

Start Time:

Finish Time:

Declaration: The attached listings represent the work of the team named above, conducted under my supervision within the times indicated according to the competition rules. I have impressed upon all team members that they must not discuss details of the tasks with any person until the conclusion of the preliminary round.

Supervisor Name:

Signed and Dated:

Summary of Tasks Attempted

Name of School:

Name of Team:

Team supervisor to complete colum headed Attempt only.

For each task, describe the team's achievement using one of these codes:

N/A Task not attempted	U/S Attempted, but unsuccessfully
PART A partially successful attempt (some apparently correct output)
OK Task completed

	Supervisor to complete	Please leave these columns blank: UNSW assessors use only
Task	Attempt	Points	Remarks
1
2
3
4
5
6
Total

Return to:

Programming Competition,
School of Computer Science and Engineering,
The University of New South Wales,
Sydney NSW 2052

by Friday 28 July 2000