Open Competition 2001

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

The detailed rules of the competition are given at 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 all the test data provided. Print out the results of each run and submit these together with the program listings. Clearly label each page with the question number and your team name.

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. There is no need to fill in an answer form on the web page this year - email submission is sufficient.

Marks will be awarded for correct behavior 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 - Jumble

Description

Write a program which, given a string, prints it out backwards with the vowels removed.

Sample Output

Input	Output
backwards	sdrwkcb
If at first you don't succeed...	...dccs t'nd y tsrf t f
Aeiouuua

Test Data


backwards

If at first you don't succeed...

Aeiouuua

Fly Fly Fly!

Gwen and Edith are very VERY funny.

"Halt!" cried the guard, running to the gate.

Constraints

You may assume the input string is no longer than 80 characters.

Task 2 - Goodbye

Description

In an exciting new TV show contestants stand in a circle and every nth contestant is removed from the circle until there is only one left. This last contestant is the winner. The number n is picked by the host.

For example, one night Ann, Burt, Charlie, Dexter, Edith, Fred, and Gwen are the contestants. The host decides the number n will be 3, and starts counting from Ann. So Charlie is removed first, then Fred, then Burt, then Gwen (the counting skips over Charlie and Fred since they have already been removed), then Edith, then Ann. Leaving Dexter as the winner.

Write a program which, given a whole number (n) and a list of strings (contestant names), prints out the name of the winner. Assume the contestants are arranged in the same order as the list of names, and that counting starts from the first contestant in the list.

The format of your output should match the examples below:

Sample Output

Input	Output
3 Ann Burt Charlie Dexter Edith Fred Gwen	The winner is Dexter
5 Ann Burt Charlie Dexter Edith Fred Gwen Pubert	The winner is Charlie
4 Ernie The Cookie monster Burt	The winner is The Cookie monster

Test Data


3

Ann

Burt

Charlie

Dexter

Edith

Fred

Gwen


5

Ann

Burt

Charlie

Dexter

Edith

Fred

Gwen

Pubert


4

Ernie

The Cookie monster

Burt


1

Bruce

Mila

Gary

Luc


5

Claire

Ann

Virginnia

Lisa

Liz

Sharon


15

Gwen

Edith

Anneka

Greta

Ned

Belinda

Natasha

Igor

Helen

Margo

Finn

Dr Who

Constraints

You may assume there are less than 50 contestants. You may assume each name is no longer than 40 characters long. You may assume n is an integer and is greater than 0.

Task 3 - Brackets

Description

A collection of brackets is well formed if opening brackets are matched by closing brackets, and if there is no overlap.

Overlap occurs when one of the brackets in a pair of corresponding opening and closing brackets is between another pair of brackets, but the other bracket in the pair isn't.

For example ([)] overlaps, but ([]) doesn't.

Write a program which, given a string consisting of bracket characters, decides whether or not the collection is well formed.

The format of your output should match the examples below:

Sample Output

Input	Output
`((()))`	`((()))` is well formed
`((([[{}[]]]))[]){}`	`((([[{}[]]]))[]){}` is well formed
`()()(]`	`()()(]` is NOT well formed

Test Data


(()())

((([[{}[]]]))[]){}

()()(]

[]

((()((())))

{[][([{}]])}

Constraints

You may assume the input contains at most 80 characters. You may assume the input does not contain any characters other than the six bracket symbols listed below:

( ) { } [ ]

Note that this list contains the curly brackets {} as well as rounded ones ().

Task 4 - Balanced Squares

Description

9 numbers arranged in a 3x3 square is said to form a Balanced Square if every row and every column has the same sum.

For example

is a Balanced Square as every row and column add up to 15.

is also a Balanced Square, every row and column add up to 6.

Write a program which, given a list of 9 integers, prints them out in a Balanced Square. If the integers can be arranged into a Balanced Square in more than one way you may print whichever one you wish.

If it is not possible to form a Balanced Square using the integers print out a message stating this.

The format of your output should match the examples below:

Sample Output

Input	Output
0 1 2 4 6 8 5 10 9	1 8 6 10 5 0 4 2 9
1 1 1 2 2 2 3 3 3	1 2 3 3 1 2 2 3 1
0 1 2 4 6 8 5 3 9	0 1 2 4 6 8 5 3 9 cannot be made into a Balanced Square.

Test Data


0 1 2 4 6 8 5 10 9

1 1 1 2 2 2 3 3 3

0 1 2 4 6 8 5 3 9

1 2 3 4 5 6 7 8 9

12 1 2 3 4 5 6 7 8

1 2 3 3 6 7 4 5 5

8 2 7 1 4 3 3 6 2

Constraints

You may assume the integers are not negative.

Task 5 - Binary Decimals

Description

The base 10 decimal 140.34 represents the sum

  1*100 + 4*10 + 0*1 + 3*(1/10) + 4*(1/100)

In a similar way the base-2 decimal 1101.101 represents the sum

  1*8 + 1*4 + 0*2 + 1*1 + 1*(1/2) + 0*(1/4) + 1*(1/8)

which is 13 + 5/8 (13.625) in base 10.

Write a program which, given two integers a and b, prints out the base-2 decimal corresponding to the fraction a/b.

If there are more than 10 digits after the decimal point print only the first 10.

The format of your output should match the examples below:

Sample Output

Input	Output
5 8	0.101
109 8	1101.101
1 3	0.0101010101

Test Data

Constraints

You may assume the inputs are integers in the range 1-1000 inclusive. You may enter the input as a string if you wish, or as an integer.

Bonus

For an additional 50%, can you get your program to print out up to 50 digits of the base-2 decimals (rather than just up to 10 digits). Note to do this you will have to be careful of rounding errors. For example the expansion of 1/3 is 0.01010101...

Provide separate printouts for the core part and the bonus part of this question. Use the same test data for the bonus part as for the core part.

Task 6 - Number Words

Description

Write a program which, given a number in digits, returns the number in words.

The format of your output should match the examples below:

Sample Output

Input	Output
13	thirteen
109	one hundred nine
1234567	one million two hundred thirty four thousand five hundred sixty seven

Test Data

Constraints

You may assume the input is an integer in the range 1-10000000 (ten million) inclusive. The words should be in lower case and not contain the word "and".

Bonus

For an additional 50%, include "and" in your output when appropriate (eg "one hundred and nine"), and accept numbers up to 100,000,000,000 (one hundred billion).

If you do the bonus part you need not provide output for the core part, although you may if you wish. Use the same test data for the bonus part as for the core part, plus the following additional test cases:

Additional Test Data for Bonus Part


100000000000

 12345600789

  1002301045

     1001327

- cut - here -

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

Open Competition 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 competition at 6pm.

Supervisor Name:

Signed and Dated:

Summary of Tasks Attempted

Name of School:

Name of Team:

Team supervisor to complete column 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
5 bonus
6
6 bonus
Total

Return to:

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

to arrive by Friday 27 July 2001