UNSW High Schools Programming Competition 2005: Open Round

Welcome to the UNSW High Schools Programming Competition 2005.

The Tasks:

  1. eCop (easy, 8 marks)

  2. Body Mass Index Calculator (fairly easy, 10 marks)

  3. ISBN Validator (moderate, 12 marks)

  4. Tournament Generator (harder, up to 16 marks)

  5. Peak Detector (part easy, part hard, up to 20 marks)

Task 1. eCop

Available Marks: 8

The Roads and Traffic Authority are thinking of installing combined red-light and speed-measuring cameras at some intersections. These new devices include licence-plate recognisers as well, so they produce a neat record of all vehicles passing the detector, comprising these three pieces of data:

To complete this task, you are to write a program that reads data from the device and determines whether or not each driver should be fined. The first line of input contains exactly 4 integers:

The remainder of the input consists of any number of lines in the format described above, one line per vehicle. Input fields are separated by space characters. Example (this is Test 1): 

60 155 75 208
TRJ893 60 green
FUNKY 55 green
XTRMN8 77 red
AA10AA 58 amber
A 68 amber
MR155 53 red
ICURMT 63 amber
SMRTAS 84 green
9999 48 broken

For every vehicle that is speeding or has run a red light your program should display the licence plate and the total fine applicable. Use fixed column widths to produce a neat table like this: 

XTRMN8 $363
A      $75
MR155  $155
SMRTAS $208

Additional Tests

As well as the above test file, you must show the output of your program when it reads this data (Test 2): 

70 155 80 213
BROKEN 0 green
CAREFL 70 green
BUSY12 74 green
BUSY23 75 green
BUSY34 76 green
ANGRY4 84 green
ANGRY5 85 green
ANGRY6 86 green
VROOM 100 green
AMBER 70 amber
RED1 70 red
RED2 75 red
RED3 85 red
RED999 86 red
AMBER 99 amber
1 111 broken
111111 11 red
IOU10U 10 red

Task 2: Body Mass Index Calculator

Available Marks: 10

The body mass index (BMI) is a measure of how appropriate a person's weight is for their height. It is a number obtained by dividing a person's weight in kilograms by the square of their height in metres. For example, a 70kg person whose height is 160cm has a BMI of 70/(1.6*1.6) = 27.34.

For adults, a BMI of less than 18.5 indicates an underweight person, 25 or more but less than 30 indicates an overweight person, and 30 or more indicates obesity.

Write a program that accepts any number of input lines, each of which contains two numbers (integers or real numbers), separated by a space. The first number is a weight in kilograms, and the second is a height in centimetres (not metres).

For each line, calculate the BMI, and display the following on one line:

Your program does not need to handle any error conditions, apart from avoiding division by zero. It will only be tested with legitimate values. For example, the four input lines (Test 1) 

61.5 158
55.29999 180.0
88 160.8
54.5 145
should produce the output 

 61.5kg  158cm  BMI=24.6  Normal
 55.3kg  180cm  BMI=17.1  Underweight
 88.0kg  161cm  BMI=34.0  Obese
 54.5kg  145cm  BMI=25.9  Overweight

Additional Tests

As well as the above test file, you must show the output of your program when it reads this data (Test 2): 

67.5 150
64 160.0
74.00000000 200
100 205

Task 3: ISBN Validation

Available Marks: 12

The International Standard Book Numbering scheme (ISBN) has been used for decades to assign a unique identifier to every book published throughout the world. It consists of 9 digits and a check-symbol (a digit or the letter X), with hyphens inserted at some places by the issuing agency.

Like many identification systems, the check symbol is used to detect if certain kinds of errors have occurred in transcribing the ISBN, such as through manual data entry. The way this works is that a formula is applied to the ISBN without the check synbol, and the result compared with the actual symbol. If they don't match, the ISBN is invalid.

The formula is this:

  1. Multiply each of the 9 digits by its position, counting the leftmost position as 1, the second from the left as 2, and so on.
  2. Add up the 9 products.
  3. Divide the result by 11, save the remainder, which of course lies between 0 and 10.
  4. If the remainder is equal to 10, the expected check symbol is the letter X, otherwise the check symbol is equal to the remainder (a single digit).

For example, 7-9851296-0-X is a valid ISBN because 

1*7 + 2*9 + 3*8 + 4*5 + 5*1 + 6*2 + 7*9 + 8*6 + 9*0 = 197 = 17*11 + 10
and the remainder of 10 matches the check symbol X.

On the other hand, 0-413-72490-3 is not a valid ISBN (the check symbol should be 5).

The Task

Write a program that reads any number of lines from input, and determines whether each line is a valid ISBN or not.

Your program should ignore punctuation, only digits and X are significant. It should display the input line, followed by either "is a valid ISBN" or "is not a valid ISBN".

Test Data

Show your program's output for the following test file 

0-413-72490-3
0-413-72490-5
0-9751194-0-0
1-56592-286-X
1234567890
123456789X
0123456789
X123456789
---0-1-2-3-4-5-6-7-8-9---
0600.587495
052148342
05214834255
#1&1+1,1;1:1|1>1.1$1

Task 4: Tournament Generator

Available Marks: 10 to 16

A round-robin tournament, where each team plays each other once, can be generated from a list of the participating teams using the following algorithm.

First assume there is an even number of teams. Write down the first half of the teams, on separate lines. Then write the second half next to them, but from the bottom to the top (this rule simplifies the generator logic).

This arrangement is the first round. For example, if the original list contains the six teams 

Koalas
Platypi
Bilbies
Thylacines
Wallaroos
Echidnas

the first round looks like this: 

Round 1:
Koalas       vs Echidnas
Platypi      vs Wallaroos
Bilbies      vs Thylacines

For each subsequent round, the first team (in this case, Koalas) retains its position, and the other teams rotate one place anti-clockwise. This means that Echidnas move across to where Platypi were, Platypi move down one place, Bilbies across and the others up.

Rounds 2 to 5 are thus: 

Round 2:
Koalas       vs Wallaroos
Echidnas     vs Thylacines
Platypi      vs Bilbies
Round 3:
Koalas       vs Thylacines
Wallaroos    vs Bilbies
Echidnas     vs Platypi
Round 4:
Koalas       vs Bilbies
Thylacines   vs Platypi
Wallaroos    vs Echidnas
Round 5:
Koalas       vs Platypi
Bilbies      vs Echidnas
Thylacines   vs Wallaroos

If there is an odd number of teams, create an extra team at the end of the list, representing a bye. The bye cycles around like the other teams, but whenever a team "plays" a bye the real team is always mentioned first, such as 

Thylacines   bye
rather than either of these 
Thylacines   vs bye
bye          vs Thylacine
For example, if Echidnas pulled out of the competition, leaving just five teams, the 5 rounds become 

Round 1:
Koalas       bye
Platypi      vs Wallaroos
Bilbies      vs Thylacines
Round 2:
Koalas       vs Wallaroos
Thylacines   bye
Platypi      vs Bilbies
Round 3:
Koalas       vs Thylacines
Wallaroos    vs Bilbies
Platypi      bye
Round 4:
Koalas       vs Bilbies
Thylacines   vs Platypi
Wallaroos    bye
Round 5:
Koalas       vs Platypi
Bilbies      bye
Thylacines   vs Wallaroos

The Task

Write a program that reads up to 10 team names, each up to 12 characters long (to produce a compact table), and generates a complete draw, including round numbers, as shown in the above examples.

Tests

You can check your program using the above examples, but we want to see your results for the following test files only:

Test 1: The Battle of the Bands

Led Zeppelin
Cog
Pink Floyd
King Crimson
Jet
Tool

Test 2: Planetary Billiards

Mercury
Venus
Earth
Mars
Jupiter
Saturn
Uranus
Neptune
Pluto

Marking Scheme

The maximum possible mark is thus 16.

Task 5: Peak Detector

Available Marks: 15 or 20

A hill vector is a sequence of numbers that consists of an ascent (numbers strictly increasing) followed by a descent (numbers strictly decreasing), with no flat regions or local peaks. For example, 

1 3 5.5 7.2 8.4 6 2.5 2
is a hill vector (with a peak at the 5th element) while 
1 3 5.5 4.2 8.4 6 2.5 2
6 5 4 3 2
1 2 2 3 4 3 2.5
are not, because the first has two local peaks (elements 3 and 5), the second doesn't have an ascent, and the third has a flat part.

For this task we extend the definition to two dimensions. Your program should detect whether a matrix of numbers contains a single peak, and if so, identify its position by row and column. To qualify, every row and every column must be a hill vector.

The first line of input contains two integers, the number of rows and the number of columns of data following. Assume there will be no more than 20 rows or 20 columns. The following data contains a peak at row 3, column 4 (counting from left to right and top to bottom, and starting at 1): 

4 6
0 1 2 3 2 1
1 2 3 4 3 2
2 3 4 5 4 3
0 1 2 3 2 1

The following does not contain a unique peak, because column 3 is not a hill vector: 

3 8
1.2 3.4 5.2 6.6 8.2 6.0 4.0 2.0
2.3 4.0 5.0 7.0 9.0 7.0 5.3 2.2
1.0 1.3 3.3 4.1 4.3 3.0 2.1 0.5

Basic Task: 15 marks

Your program should determine whether the input contains a single peak. If so, it should report the coordinates in this way: 
peak found at row 3 column 4

If there is no single peak, the appropriate response of the form 

row N is not a hill vector
   or
column N is not a hill vector
where N is a row or column number. You should test the rows first, and then the columns.

Up to 10 of the 15 marks may be awarded if your program can correctly identify a peak in a matrix that has just one row (a single vector).

Extension

Warning: requires some knowledge of HTML tables.

An additional 5 marks is available for the following extension.

We would like to visualise any data with a valid peak, assuming it to be sampled elevations (heights above sea level). For example, Mt Kosciuszko is quite a rounded peak with a spur oriented towards the north, as you can see from this picture.

It's an image derived from an HTML table, generated from the data in Test 4. To create one of this kind, you need to produce an HTML document that looks like this: 

<html><head><link rel=stylesheet href="http://www.cse.unsw.edu.au/~progcomp/spectrum.css">
</head><body>
<table>
    ...

</table>
</body></html>
Inside the table is a series of rows, and the data elements look like this: 
<td class="bg08">&nbsp;</td>
The colour of the cell is determined by the two-digit number following the bg, defined in the linked style sheet: it ranges from 00 (the smallest number, green) to 44 (the peak, red). You will need to determine the range of numbers, and scale them linearly to the range 0 to 44.

If you attempt the extension you should paste the complete HTML file generated from Test 4 into the test box.

Test Data

Test 1

1 9
2 4 5 12 17 22 21 10 5

Test 2

3 7
2.3 4.5 8.2 7.1 8.1 3.0 1.5
3.4 4.8 10 8.4 8.2 5 3
1 2 3 4 3 2 1

Test 3

5 6
1 2 3 2 1 0
2 3 5 6 10 4
3 5 7 8 9 6
2 3 4 5 8 7
1 2 3 6 2 1

Test 4

12 13
2091.4 2112.4 2140.0 2135.7 2112.7 2077.4 2043.4 2024.3 2005.4 1992.4 1980.0 1965.1 1957.0 
2092.2 2112.9 2141.7 2147.8 2132.0 2100.1 2061.5 2034.8 2017.4 2001.2 1984.2 1968.9 1960.0 
2095.0 2113.2 2142.2 2157.9 2150.8 2121.7 2083.0 2043.8 2023.1 2007.9 1996.3 1976.3 1963.9 
2098.0 2118.7 2142.5 2171.0 2169.4 2135.9 2100.2 2067.4 2036.3 2018.3 2003.3 1983.9 1974.8 
2104.9 2123.5 2152.7 2187.0 2187.4 2152.3 2110.4 2082.4 2048.6 2026.7 2011.6 1991.2 1980.0 
2105.8 2128.6 2159.7 2189.8 2196.7 2171.2 2136.5 2089.7 2060.6 2033.9 2017.9 1997.7 1981.1 
2112.4 2139.2 2160.1 2190.7 2202.9 2189.2 2158.8 2111.8 2070.7 2043.1 2025.7 2003.7 1989.6 
2125.1 2144.0 2167.9 2199.6 2218.0 2206.5 2175.3 2135.5 2084.7 2058.8 2039.9 2023.3 2002.2 
2132.2 2149.0 2178.6 2205.4 2228.0 2209.4 2177.0 2141.4 2098.4 2070.5 2041.1 2029.2 2006.6 
2132.6 2147.7 2180.5 2201.7 2209.6 2198.2 2170.7 2141.8 2101.7 2077.8 2042.0 2029.8 2013.3 
2121.9 2140.6 2164.9 2187.4 2193.6 2180.7 2157.8 2134.0 2105.1 2074.1 2043.8 2029.5 2021.2 
2114.9 2135.0 2154.3 2176.6 2180.0 2167.1 2148.8 2125.6 2104.3 2069.4 2043.1 2027.7 2021.0