## UNSW High Schools Programming Competition 2008: Open Round

Welcome to the UNSW High Schools Programming Competition for 2008.

• You have 2 hours.
• Submissions after the deadline will be marked as LATE and will not be marked unless prior arrangements have been made.
• You may solve the tasks in any order.
• Tasks are of differing value and difficulty.
• You may submit multiple times for each task. Only your most recent submission will be marked.
• You are reminded that only genuine output from a working program and the program text itself is to be pasted into the submission boxes. Hand-crafted output will result in the team's disqualification.
• Good luck and have fun!

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)

### 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

• Correct Naismith value for first set of data: 2 marks
• Correct Tranter adjusted value for first set of data : 2 marks
• Correct value for other cases: 3 marks
• Times correctly rounded to 5 minutes: 2 marks

### 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:

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 = r – a angle = 2 sin–1(c / 2r)

If your programming environment doesn't have an inverse sine function, you may need to use the relation

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

• Correct value for first sagitta: 2 marks
• Correct value for first angle: 2 marks
• Correct value for other valid cases: 3 marks
• Detecting errors: 2 marks

### 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

• Word contains other than lower-case letters (report the word).
• Inconsistent word length (report the first word with length different from the previous word).
• Word differs by more than one character from the previous one (report the word).
• Word occurs more than once (report the word).

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:

• Even numbers (divisible by 2)
• Triangular numbers (equal to the sum of the first n integers, beginning 1, 3, 6, 10, 15...)
• Fibonacci numbers (Fn = Fn–1 + Fn–2 and F1 = F2 = 1, beginning 1, 1, 2, 3, 5, 8, 13, 21,...)
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

• Correct identification of even minimax: 5 marks
• Correct identification of triangular minimax: 3 marks
• Correct identification of Fibonacci minimax: 3 marks
• Correct identification where no solution exists: 1 mark

### 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

• Correct ELS: 8 marks
• Correct ELS in context: 6 marks
• Correct identification of puzzle ELS: 6 marks