UNSW High Schools Programming Competition 2011: Open Round

The Tasks:

Junior task: Team Count (easy, 10 marks)

  1. Roman Chronogram (easy, 7 marks)
  2. Triangles (easy to moderate, 9 marks)
  3. Darts (moderate, 11 marks)
  4. Mid Square Sequences (moderate, 14 marks)
  5. Word Squares (moderate to hard, 19 marks)

Junior Task. Team Counts

Available Marks: 10

The Progcomp 2011 rules state:

In addition to any number of teams of three, each high school will be allowed to register exactly ONE or TWO teams of 2 students.

A high school with a single outstanding student may register a team consisting only of that student, but only if no other team is registered from that school.

Write a program that, given the number of participants a school has (1 or more), determines exactly how many teams of 3, teams of 2 and teams of 1 the school is allowed to register.

The first line of input to the program is the number of schools, followed by the number of participants for each school, each on a separate line. No other information is provided or needed.

The program should show the number of participants and how many teams of each size, using singular or plural terms as appropriate ("team" vs "teams"), and omitting mention of zero cases. Use the format shown below, including a comma to separate items and a full stop at the end. Marks are awarded both for computational correctness and following the format.

Example

Input:
4
7
9
2
1

Output:

7 participants = 1 team of 3, 2 teams of 2.
9 participants = 3 teams of 3.
2 participants = 1 team of 2.
1 participant = 1 team of 1.

Test Data

You should test your program on the following data:
9
3
22
1
8
120
121
4
5
2

Task 1. Roman Chronograms

Available Marks: 7

A chronogram is a phrase in Latin or another language, that embeds a date in roman numerals. To decode it, extract each roman numeral (capital letters only) and add up their face value, regardless of the order in which they occur. For example, "My Day Closed Is In Immortality" (commemorating the death of Elizabeth I in 1603) contains the roman numerals MDCIII, which is 1000 + 500 + 100 + 1 + 1 + 1 = 1603. In this case the order is preserved (a natural chronogram), but this is not essential.

Roman numerals and their values are shown in the table below.

M = 1000
D = 500
C = 100
L = 50
X = 10
V = 5
I = 1

Write a program that reads a number of phrases and calculates the chronogram value for each one. The first line of input indicates the number of phrases, each of which can have up to 150 characters, followed by the phrases, one per line.

For each phrase your program should display the chronogram value followed by the phrase.

Example

Input:
6
SAVVY PROGRAMMERS VEX CHURLISH TESTERS
some roman numerals but they're in the wrong case, except thIs one.
FIRE STARTS IN THE KING'S BAKERY, THEN LONDON IS BVRNING, CONSVMEd BY THE INFERNO.
note the sneaky olde-style use of V instead of U in the previous example
My Mother Plays the Xylophone Intently
EXPECT THE DEVIL

Output:

 2176  SAVVY PROGRAMMERS VEX CHURLISH TESTERS
    1  some roman numerals but they're in the wrong case, except thIs one.
 1666  FIRE STARTS IN THE KING'S BAKERY, THEN LONDON IS BVRNING, CONSVMEd BY THE INFERNO.
    5  note the sneaky olde-style use of V instead of U in the previous example
 2011  My Mother Plays the Xylophone Intently
  666  EXPECT THE DEVIL

Test Data

You should test your program on the following data (note that the browser may wrap lines 5 and 7, the 4th and 6th test cases, but should copy them correctly to the clipboard):
12
AFTER A LONG, PERILOVS JOVRNEY, COLVMBVS EXVLTANTLY SHOWS THE WAY TO AN VNKNOWN CONTINENT.
MICHELANGELO, SCVLPTOR / PAINTER STARTS TO PAINT THE CHAPEL ROOF.
INTERESTING DISCOVERY FOR COOK, NAVIGATOR IN THE ENDEAVOUR: THE GREAT SOUTHERN LAND.
THE FIRST FLEET (SIX CONVICT TRANSPORTS, THREE STORE SHIPS + TWO NAVAL ESCORTS) ARRIVES AT SYDNEY COVE, LED BY CAPTAIN ARTHUR PHILLIP.
ALEXANDER GRAHAM BELL CAN VERIFY INVENTION OF THE INITIAL TELEPHONE.
INTERNATIONAL CONTESTS BETWEEN ATHLETES ARE HELD AT ATHENS: A WAY OF REVIVING ANCIENT WARRIOR GAMES, OR A VERY EXHAUSTING EXHIBITION OF FITNESS?
TITANIC MAKES DISASTROVS COLLISION WITH AN ICEBERG.
VENTURE TO CELEBRATE LUNAR EXCURSION: A GIGANTIC LEAP FOR MANKIND.
More tests, including case sensitIVITY
USING AXES, LUMBERJACKS VERY QUICKLY FELLED THE WIZARD'S PINE FOREST (quick brown fox analogy)
CDs versus DVDs
nothing

Task 2. Triangles

Available Marks: 9

Write a program that, given the lengths of the sides of a triangle, does the following:

  1. Determines whether the triangle exists at all, that is, each side is positive and they all can meet at the vertices;
  2. If it's a valid triangle, calculates its area using Heron's Formula below; and
  3. If it's a valid triangle, determines which type of triangle it is, according to the standard classification:
    • equilateral (all sides equal), isosceles (two sides equal) or scalene, and
    • right-angled, acute (all angles less than 90 degrees) or obtuse (one angle more than 90 degrees).

A neat summary of the 7 possible triangle types is this diagram, first published in 1901 (there aren't 9 types because equilateral triangles can only be acute):


Wentworth and Hill (1901), First Steps in Geometry.

Heron's formula calculates the area A using the lengths of the sides a, b, c:

where the semiperimeter s is given by

If a is the longest side, then the largest angle α opposite it can be calculated from the cosine rule:

Should you need to know, π is approximately 3.141592653589793238462643383279502884197169399375105820974944592307816406286…

Equality Test

For the purposes of this task, if the difference between two quantities is less than 10–8 in absolute value they are considered to be equal.

Input/Output Formats

Each line of input after the first consists of three real numbers, representing the sides of a (possible) triangle, separated by spaces. The first line contains the number of triangles to be classified (up to 20).

Your program should display the three sides, then either the phrase "is not a triangle" or the above classification (both words, such as "scalene & right-angled") followed by the calculated area in any convenient format. Don't show the area if it isn't a triangle.

Example

Input:
4
3 5 4
10 67 13
1.5 1.5 1.5
4.78 9.6321 5.043

Output:

3 5 4 is scalene & right-angled. Area = 6
10 67 13 is not a triangle.
1.5 1.5 1.5 is equilateral & acute. Area = 0.974278579
4.78 9.6321 5.043 is scalene & obtuse. Area = 4.63893981

Marking Scheme

5 marks for the classification and 4 for areas.

Test Data

You should test your program on the following data:
11
2 3 2
1 2 3.000001
10.000000001 10.000000004 9.999999999
-4 4 4
123.5 200 167.2
4 1 4.123105625
30 15 16
11.5 11.5 16
5 0 8
5.7 8.0610173 5.7
999 99 9

Task 3. Darts

Available Marks: 11

In the game of darts each player throws up to three darts at a time onto the dartboard, scoring points for hitting various regions of the board. The aim is to count down from a starting value (usually 501 points), reaching exactly zero. Players alternate with three darts each.

Scoring Notation

There are several different scoring regions on a dartboard, as shown in the picture. N represents a number between 1 and 20, according to the sector in which the dart lands.

Region Effect on Score Notation
Single score sectors Score the sector value SN
Outer (double) ring Score double the sector value DN
Inner (triple) ring Score triple the sector value TN
Outer bullseye Score 25 points OB
Inner bullseye Score 50 points IB

For example, if three darts are scored as D20, OB and T7 the total score would be 2*20 + 25 + 3*7 = 86 (this is not the optimal way to reach 86, however).

Write a program that can determine what scores a player should aim for for each of their darts in order to reach a specified target score exactly. If there is no possible way of reaching the target score then a combination of darts that gets closest to the score without exceeding it should be generated. Scores should be in decreasing order of value, and solutions don't have to use all three darts.

The input file has a score (a positive integer) on each line, with the first line giving the number of scores to be processed (up to 30). The program should display the target score, a : symbol, up to three scores separated by + symbols, an = and what they add up to.

Marking

As well as producing a solution that adds up to the appropriate score, to maximise the available marks your program must follow these rules:

Hint

You might find this task easier if you first systematically generate a table containing all 180 different solutions.

Example

Input:
5
15
34
79
1
200

Output:

15: S15 = 15
34: D17 = 34
79: T20 + S19 = 79
1: S1 = 1
200: T20 + T20 + T20 = 180

Test Data

You should test your program on the following data:
23
5
8
18
21
25
28
31
44
83
85
93
101
103
120
141
145
150
161
163
176
177
180
501

Task 4. Mid Square Sequences

Available Marks: 14

An old, though seriously defective, way of generating pseudo-random numbers (apparently random but determined by an algorithm) is the so-called Mid Square Method. Although it works for various lengths, for this task we are restricting it to numbers with 5 decimal digits (including the digit 0).

Take a 5-digit integer. This is called the seed for the sequence. Square it, if necessary padding the result on the left with zeroes to make exactly 10 digits. Extract the middle 5 digits from the result (actually drop the first 2 digits and extract the next 5, as 10 digits doesn't have a unique middle). This number is the next one in the sequence. Repeat as many times as desired.

Implementation note: 10 decimal digits requires 34 bits to represent: if you have a choice of types you may wish to do your calculations using double precision floating point.

Definitions:

The problem with the method is that the sequence eventually, and sometimes quickly, ends up in a short cycle. For example, if a sequence reaches 00000 the next number is also 00000 and so on. If the seed is 64493 its square is 4159347049, so the sequence goes

64493  59347  22066  86908  53000  09000  81000  61000  21000  41000
The next number is 81000, so this sequence, of length 10, ends in a cycle of length 4 (bold).

Write a program that generates mid-square 5-digit sequences. Use it, along with any filtering or analysis tools you happen to have available (or can write quickly) to answer the following seven questions (2 marks each):

  1. What is the 100th element (where the first is element 1) of the sequence whose seed is 55555?
  2. Besides 00000, which seeds are degenerate (are cycles of length 1)?
  3. How many sequences have length exactly 200?
  4. Four sequences have maximal length (that is, no longer sequence exists). What is this length?
  5. What is the seed for each of the maximal-length sequences?
  6. There are two cycles of length 4, one of which is shown in the example above. What is the other one?
  7. What is the length of the longest cycle?

Task 5. Word Squares

Available Marks: 19

Charles Babbage, computing pioneer, is credited with the game of word squares, where n n-letter words are arranged in a grid so that they read the same from left to right and from top to bottom. The following are examples of word squares:

T O E    B A B Y    F R I L L    R E A C T S
O N E    A R E A    R O D E O    E X P O R T
E E L    B E E R    I D E A S    A P P E A R
         Y A R D    L E A P S    C O E R C E
                    L O S S Y    T R A C T S
                                 S T R E S S

Write a program that can generate word squares from a list of words in upper case, all of the same length (at least 3 and no more than 6). For full marks you will have to produce a single word square, one that uses the largest number of different letters of all word squares obtained from the word list. If there are multiple word squares with the same number of different letters, any one will do.

Input to the program is just a list of words. If there is no solution, the program must state this, otherwise it should display the selected solution in the format shown in examples. Two of the data files are fairly long, and are provided as links rather than shown on this page.

Example

Input:
LAST
OPUS
CATS
DOGS
POST
STOP
NEXT
PIGS
TYPO
COWS

Output (this uses just 6 different letters but is the only solution):

S T O P
T Y P O
O P U S
P O S T

Test Data

You should test your program on the following three data sets. Part marks are given for valid word squares that don't use the largest number of different letters.

Test 1 (15 words) Test 2 (66 words) Test 3 (3138 words)
JIG
WIN
PUN
AGE
ICE
LAD
SEA
SAG
POD
EGG
GNU
FLY
TIN
ART
YES
Unix line terminators

Windows line terminators
Unix line terminators

Windows line terminators
Reference: based on the exercise Squaring the Bishop, 3 May 2011, from Programming Praxis (programmingpraxis.com).