UNSW High Schools Programming Competition 2008: Open Round

Welcome to the UNSW High Schools Programming Competition for 2008.

The Tasks:

  1. Naismith's Rule (easy, 9 marks)
  2. Chord Calculations (easy to moderate, 9 marks)
  3. Word Ladder Checker (moderate, 10 marks)
  4. Minimax Sequence Elements (easy to moderate, 12 marks)
  5. Bible Codes (moderate to hard, 14 to 20 marks)

Task 1. Naismith's Rule

Available Marks: 9

W W Naismith was a Scottish climber who in 1892 devised a rule to estimate the time required for a group of very fit people to walk a given total horizontal distance and vertical ascent. After variations to account for most walkers not being mountaineers, Naismith's Rule can be reduced to an equation

t = 3.5d + h/500 [incorrect]
t = d/3.5 + h/500
where t is the walking time in hours, d is the total distance in kilometres and h is the ascent in metres.

A further adjustment suggested by fellow Scot Philip Tranter adds time due to fatigue for walks of more than three hours:

t′ = 0.02t2 + 1.19t – 0.75
where t is the adjusted time in hours, provided t is more than 3.

Write a program that reads a number of lines from input, each containing a distance in km and an ascent in m. For each set of data, the program should display the input values, then the walking time according the Naismith's Rule, and finally the adjusted walking time according to Tranter's correction.

2 marks are reserved for displaying times in h:mm format, with the minutes rounded to the nearest multiple of 5 and displayed with exactly two digits.

The first line of input contains the number of test cases. You may assume that each line contains two non-negative numbers in integer or real number formats. There may be up to 10 test cases.

Example

Input:
4
8 0
2.8 150
12.5 400.0
21 650

Typical output:

Distance:  8.0km ascent:    0m  Naismith time:  2:15  adjusted time:  2:15
Distance:  2.8km ascent:  150m  Naismith time:  1:05  adjusted time:  1:05
Distance: 12.5km ascent:  400m  Naismith time:  4:20  adjusted time:  4:50
Distance: 21.0km ascent:  650m  Naismith time:  7:20  adjusted time:  9:00
(The last one is the Lakes Walk circuit from Charlotte Pass via Mt Kosciuszko summit.)

Test Data

You should test your program on the following data.

Test 1

10
10 750
1.8 0
3.5 0
10 0
10 71.428571428571428571428571428571
5.5 1000
10 1220
16.5 500
22 600
26 1000

Marking Scheme

Task 2. Chord Calculations

Available Marks: 9

A chord is a straight line touching a circle at two points. Some strange names are given to the two parts of a line that runs from the centre of the circle to the arc, bisecting the chord:
sagitta definition
Ref: Wolfram Demonstrations Project.

The sagitta is the line from the midpoint of the chord to the arc, while the line to the centre is called the apothem.

Write a program that, given the radius of the circle and the length of the chord, calculates the length of the sagitta, and the angle subtended by the chord in degrees. We always want the smaller of the two possible arcs.

Formulas

Although the formulas can be derived fairly easily, so you can spend your time on the programming effort, here are the relevant equations:

Given r = radius; c = chord length
apothem a: a2 = r2 – (c/2)2
sagitta s = ra
angle = 2 sin–1(c / 2r)

If your programming environment doesn't have an inverse sine function, you may need to use the relation arcsin(x)=arctan(x/sqrt(1-x^2))

Test input consists of a line containing the number of test cases, followed by a pair of numbers representing each test, radius followed by chord length.

Your output should be one line per test, consisting of the input values and either the two calculations above correct to at least 4 decimal places, or an error message if the data is invalid. To be valid, the radius must be positive and the chord length must lie between 0 and twice the radius (inclusive).

Example

Input:
4
2  2.0
36.2 50.00000
14.5  30
-4   2

Output:

  2.0000   2.0000 s =   0.2679   angle =  60.0000 degrees
 36.2000  50.0000 s =  10.0191   angle =  87.3565 degrees
 14.5000  30.0000 Chord is too long
 -4.0000   2.0000 Radius is non-positive

Assumptions

Each test will consist of two numbers in integer or real format. There will be no more than 20 sets of data (not that it should matter).

Test Data

You should test your program on the following data.

Test 1

10
5 6
123.4 200
5.6 0.85
25.6721 36.30582
100 200
1 0
50 100.001
3.56 -2
0 0
-4 4

Marking Scheme

Task 3. Word Ladder Checker

Available Marks: 10

A word ladder is a list of words of the same length, with each word differing from the one before it in exactly one letter:

love
hove
have
hate
The game requires all the words to be in the dictionary (and the start and end words should be antonyms), but we will only worry about the syntax of word ladders, not their semantics.

Write a program that analyses word ladders and identifies the first error that occurs in each one, if any. Errors to be detected are

The first check applies to all words, the other to all but the first word. If no error is detected, display the word "Feasible".

Data Format

The first line of input shows the number of ladders, followed by one ladder per line. Each ladder begins with the number of words, followed by the list of words in order, separated by a space. Each word has at least 1 character and at most 10 characters, and no ladder is longer than 20 words.

The output should repeat the word list and report the results of the analysis on the next line, slightly indented for clarity.

Example

Input:
5
4 cat cot cog dog
4 love hive have hate
11 nerd herd hard card cord cork core corn cork cook cool
2 bright dark
6 sl33t sh33t sh33r sh34r sp34r sp34k

Output:

cat cot cog dog
  Feasible
love hive have hate
  Too many changes to produce "hive"
nerd herd hard card cord cork core corn cork cook cool
  Repeated word "cork"
bright dark
  Inconsistent word length for "dark"
sl33t sh33t sh33r sh34r sp34r sp34k
  Non-letters in "sl33t"

Test Data

You should test your program on the following data.

Test 1

8
14 frown crown croon crook crock chock shock shack stack stick stalk stale stile smile
7 brown grown groan groat great greet green
16 great greet greed breed bread bred bleed blend bland blank black slack stack stalk stall small
2 hero zero
11 cain fain fail fall fill full fell fill file aile able
7 o i c u r m t
4 batt bait bai1 ba11
7 less loss lose lost love move more

Task 4. Minimax Sequence Elements

Available Marks: 12

Write a program that identifies in a sequence of positive integers the largest and smallest occurrences of the following kinds of number:

Input consists of any number of lines, each containing any number of positive integers in any order. The sequence is terminated by the value 0.

Your output consists of one line for each of the number types described above, listing the minimum and maximum values found, or the word "None" if the sequence doesn't contain any of that type.

Example

Input:
7  21  66  57 11
561 563 6765 559 16765

105 37 333 6567 7665
99 0

Output:

Even numbers:         min 66 max 66
Triangular numbers:   min 21 max 561 
Fibonacci numbers:    min 21 max 6765

Assumptions

There will be no more than 100 numbers. No number will be more than one million.

Test Data

You should test your program on both of the following sets of data.

Test 1

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

Test 2

7664 71994 9096 71785 26 904 668944 78 46 3869 64043
927 97 45923 49 790 360 29986 618 832040 30 77419
27 529 456 268052 5279 3832 28 67 23396 70500 3876
57 883 27 73734 924 144 6164 221 307 41 6753 75584
27191 61 3413 12 255255 5750 5104 99 3146 316 972 90
1069 8050 3472 60119 49 984 150910 48165 52829 3513
28 408 121393 21076 69218 678 877820 20348 7866 938
37 159 75534 81163 743219 74670 0

Marking Scheme

Task 5. Bible Codes

Available Marks: 14, plus 6 available bonus marks

Some people believe that messages are hidden in certain sacred texts in the form of sub-texts formed by taking every k-th letter for some value of k. All non-letters are ignored in counting character positions. For example, starting at the fifth letter and marking every sixth letter of the phrase

"An apple a day keeps the doctor away, usually."

produces the word (or name) "pascal". Such sub-texts are called Equidistant Letter Sequences, or ELS, and when applied to versions of the bible are also known as Bible codes.

Write a program that can extract an ELS given its positional parameters. The program should accept a (potentially very long) piece of text, and three integers:

  1. The position in the text to start, counting the first letter of the text as position 1 (1 or more),
  2. The cycle length, how many text letters there are between extracted letters (must be non-zero), and
  3. The length of the extract (0 or more).

For 8 marks, the program should display the ELS found at the specified position. Note that the cycle length can be negative, to extract an ELS that appears backwards in the text. Letters in the ELS can be mapped to one case if you like.

For an additional 6 marks, the program should display all lines of the text that contain part of the ELS, with the ELS characters bracketed, as [x]. All original formatting, character order and letter case should be retained. Only the relevant lines should be extracted, followed by the ELS as above.

Example

The following is a small excerpt from Bram Stoker's Dracula (1897).
In the library I found, to my great delight,
a vast number of English books, whole shelves
full of them, and bound volumes of magazines
and newspapers. A table in the centre was
littered with English magazines and newspapers,
though none of them were of very recent date.

For the input values (offset, cycle and length)

102 5 7
a correct program should produce
full of them, and bound volumes of mag[a]zine[s]
and n[e]wspa[p]ers. A [t]able [i]n the [c]entre was

aseptic

It's up to you how your program obtains the text and the search parameters.

Test Data

You should test your program on each of the four sets of parameters below, using this excerpt from the Book of Genesis:
So Isaac dwelt in Gerar and the men of the place asked him
of his wife and he said, "She is my sister," for he feared to say
"She is my wife", lest, said he, "the men of the place
should kill me for Rebekah because she was fair to look upon"
and it came to pass when he had been there a long time that Abimelech,
king of the Philistines, looked out at a window and saw, and, behold,
Isaac was sporting with Rebekah his wife and Abimelech called Isaac
and said, "Behold of a surety she is thy wife and how saidst thou
'she is my sister'?" and Isaac said unto him, "Because, I said, lest I
die for her."
Genesis 26:6-9. King James version.

Test Parameters

72 1 6
416 12 4
465 -36 5
427 -100 5

A Final Puzzle

Using your program, an adaptation of it, and/or other tools, find the only intelligible 21-character ELS that starts with "iva" in this scrambled version of Dracula (13893 lines, 825kb zipped to 337kb). The cycle length for this ELS is equal to 12 and the first three letters appear on the same line.

Marking Scheme