CSE/UNSW/CISRA High Schools Programming Competition 2002

Preliminary Round, Open Competition

Task 1 - Digital Roots

Description

The digital root of a number is the one digit sum of its digits.

For example the digital root of 24 is 6 (2+4=6).

If the sum has more than one digit then repeat the process over and over again until a single digit remains.

For example the digital root of 9299 is 2 (9+2+9+9=29, and 2+9=11, and 1+1=2)

You are to write a program which, given a non-negative integer, calculates and prints its digital root.

Examples

Test Data

Constraints

You may assume the number given is an integer between 0 and 10⁸⁰ inclusive.

Task 2 - Amicable Numbers

Writing a program which determines whether a pair of numbers are amicable numbers. Amicable numbers are two numbers such that the sum of each one's positive factors (except for itself) equals the other number. The smallest known pair is 220 and 284.

For example, the factors of 220 are [1,2,4,5,10,11,20,22,44,55,110] which sum to 284, and the factors of 284 are [1,2,4,71,142] which sum to 220.

Examples:

Test Data

Task 3 - Combinations

Description

Write a computer program to generate all the possible combinations of n letters, choosing from m letters. Your output should match the format of the sample output, i.e. each combination on a separate line.

The input is a pair of integers m and n. Print all combinations of n letters drawn from the first m letters of the alphabet.

Your output must not contain duplicate combinations. Note that combinations ignore order. For example: ABC is the same combination as CBA (even though the order is different).

Examples

Test Data

Constraints

You may assume that 0 < n <= m <= 26.

Bonus Marks

Bonus marks will be awarded for a constructive solution, i.e. one which internally only generates valid combinations (as opposed to a solution which has to at some point go through eliminating invalid/duplicate combinations).

Task 4 - Packing Weights

Description

You have a supply of weights, and you need to load them into paper bags for transportation. However, each bag can only carry 10 kg. Any more weight than this would break the bag. Given a list of weights (in kg), you will need to determine an 'optimal' arrangement for transporting the weights. An optimal arrangement uses the least number of bags possible.

Write a program which, given a list of weights, returns an optimal arrangement. Output must match that shown below (with each bag's contents listed on a separate line). You may list the bags in any order.

Examples

Test Data

Constraints

You may assume every number in the input is an integer and lies in the range 1 to 10 inclusive. You may assume no more than 25 weights will be given.

Bonus Marks

You will receive the bonus marks if you also find a most balanced optimal arrangement. This is an optimal arrangement such that the largest bag-weight is a minimum. (If there is more than one most balanced arrangement, you can return any of them)

Example

We are given weights 7, 3, and 5 kg. Clearly an optimal arrangement uses 2 bags. But we could have 7/3 in one bag and 5 in another, or 7 in one bag and 5/3 in the other. The most balanced arrangement is 7 in one bag and 5/3 in the other because then the largest weight of a bag is 8 kg, whereas 7/3 and 5 would give a largest weight of 10 kg.

Test Data

As above. But, if you attempt the bonus marks, use the wording "A most balanced optimal arrangement" instead of "An optimal arrangement".

Examples

Task 5 - Inside/Outside

Description

Write a program which, given a list of co-ordinates of the vertices of a convex polygon, and then some other point, determines whether or not that point is inside the polygon. Your output is to match that of the sample output.

A convex polygon is one such that from any vertex, you can see every other vertex (direct line of sight) without going outside the boundary of the polygon. Another way of putting it is that a polygon is convex if and only if every internal angle is less than 180°.

A Convex polygon	NOT a convex polygon
	(Note how the line AC would be outside of the polygon, and the internal angle at B is greater than 180°)

Note: Points on the boundary of the polygon are regarded as being inside the polygon.

Test Data

Sample Output

Constraints

You may assume all ordinates are integers and non-negative. You may assume the polygon has no more than 25 vertices. You may assume the vertices of the polygon are given in adjacent order.

Bonus Marks

Bonus marks will be awarded for a solution which does not assume that the vertices are in adjacent order.

Test Data

Sample Output

Task 6 - Paint Fill

Description

You are to write a program, which given several lines of text representing a picture, must fill the inside of an object.

Empty space will be indicated by '-' characters. The border of the object is indicated by '*'s. The filled image should be returned, also using '*'s. To aid you, one point inside the object to be filled will be given. It will be identified by an 'o'.

Test Data

---***--
-**---*-
-*-----*
-*-o--*-
--****--

-**---**-
*o-*-*--*
*---*---*
-*--*--*-
--*---*--
---*-*---
----*----

*******--
*------*-
-*****--*
------*o*
***---*-*
*-****--*
*------*-
-******--

--***--**-
-*---***-*
*------*-*
*-o--*---*
*---*-**-*
-*-*---***
--*-------

Sample Output

---***--
-******-
-*******
-******-
--****--

-**---**-
****-****
*********
-*******-
--*****--
---***---
----*----

Constraints

You may assume the lines of text will be rectangular. The line-length will be no more than 80 characters, and there will be no more than 24 lines.

You may assume there are no "pinched" shapes such as the figure 8 below:

--**--
-*--*-
-*-o-*
-*--*-
--**--
-*--*-
-*---*
-*--*-
--**--

Summary of Tasks Attempted