## UNSW High Schools Programming Competition 2007: Open Round

Welcome to the UNSW High Schools Programming Competition for 2007.

• 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.
• Good luck and have fun!

1. Time Flies Like an Arrow (easy, 12 marks)
2. Golden Ratio (easy to moderate, 8 marks)
3. Index Generator (easy, 10 marks)
4. Josephus Problem (moderate, 18 marks)
5. Maximal Subsequence Sum (moderate to hard, 12 marks)

## Task 1. Time Flies Like An Arrow

### Available Marks: 12

The 24-hour system of time uses four digits to represent a time to the nearest minute between midnight (0000) and one minute to midnight on the same day (2359).

Write a program that converts a list of 4-digit numbers into the corresponding 12-hour times, using one of the formats

hh:mm AM hh:mm PM Where hh is the hour (1 to 12) and mm is the number of minutes (00 to 59).

The first input line contains the number of time values. The remainder of the input consists of one 24-hour time per line. For each input line, display the original time and the corresponding 12-hour time. You may assume that each input consists of exactly 4 digits, but if the number does not represent a valid 24-hour time you must show a suitable error message, instead of the 12-hour value.

### Example

Input:
 ```4 0509 1685 2933 2259 ```

Output:

 ```0509 5:09 AM 1685 Invalid time 2933 Invalid time 2259 10:59 PM ```

### Test Data

You should test your program on the following examples.

#### Test 1 (all valid times)

 ```6 0138 0700 1001 1234 1333 2345 ```

#### Test 2 (some times valid, some invalid)

 ```11 2359 2400 0000 0099 0444 1111 0660 1551 1666 2222 3333 ```

### Marking Scheme

You may be awarded some marks if your program can process a single input time correctly.
• Correct handling of the first input on each test: 4 marks
• Correct handling of all valid times: 6 marks.
• Correct identification of invalid times: 2 marks.

### Important Note

Do not be tempted to edit your program's output or fabricate results in any way. This is an easy problem for humans, not exactly trivial for a computer.

### Available Marks: 8

The Fibonacci sequence (yes the same one used in the Trial Question) has some interesting properties. In case you missed the definition, the first two values of the Fibonacci sequence are 1 and 1, and every other value is the sum of the two previous values. The first dozen Fibonacci numbers are thus

```1  1  2  3  5  8  13  21  34  55  89 144...
```
One of the sequence properties is that the ratio of successive Fibonacci numbers converges to an irrational number called the Golden Ratio. The first few calculated ratios are 1/1 = 1, 2/1 = 2, 3/2 = 1.5, 5/3 = 1.6666..., 8/5 = 1.6, 13/8 = 1.625, 21/13 = 1.6153846..., 34/21 = 1.6190476..., which you can see are starting to converge. Rectangles with sides in the Golden Ratio are considered to be more aesthetically pleasing than other ratios.

Write a program that calculates the Golden Ratio to high precision. It must do so by generating successive Fibonacci pairs until the ratio p of the pairs is found such that

abs(p2p – 1) < 10–14

where abs(x) represents the absolute value of x.

For example, if you use the last ratio above p = 1.6190476, p2p – 1 = 0.002267531 which is a lot bigger than 10–14.

The program does not require any input. It must output the following values:

1. The value of p, to at least 12 decimal places
2. The value of p2p – 1
3. The Fibonacci pair (both numbers) whose ratio is p

Use double-precision real arithmetic if possible.

### Marking Scheme

This task is worth 8 marks. Marks may be deducted for incorrect identification of the first Fibonacci pair sufficient to produce the required ratio.

### Available Marks: 10

Write a program that generates a simple index from a list of words, one per line. The index shows each word and the position of the word in the list, counting from 1. It must be formatted so the word and the position are separated by dots and the last character of the position number is in a fixed column. The first line of input gives the number of words followed by the required width.

### Example

Input:
 ```10 15 Time flies like an arrow but fruit flies like a banana Groucho Marx ```

Output (for 10 marks):

 ```Time..........1 flies.........2 like..........3 an............4 arrow.........5 but...........6 fruit.........7 flies.........8 like..........9 a............10 banana.......11 Groucho......12 Marx.........13 ```
Two extra marks are awarded if the index is sorted by word (case-insensitive).

You may assume that there is always room for at least one dot. A word is any sequence of characters, including spaces and punctuation.

### Test Data

You should test your program on the following example.

#### Test 1

 ```17 22 Amazon Po Nile Murray-Darling Congo Rio Grande Ganges Mississippi-Missouri Niger Lower Tunguska Mekong Danube Zambesi ..... . Colorado 171717171717171717 ```

### Marking Scheme

• Correct index generation: 8 marks
• Index sorted by word: 2 marks.

### Available Marks: 18

Flavius Josephus was a first century CE Jewish historian and soldier. According to legend, he and 40 other soldiers were trapped in a cave by the Romans. Rather than surrender, the group entered into a suicide pact, whereby they would stand in a circle and every 3rd man standing would be killed, the last one by his own hand. It is said that Josephus and a friend positioned themselves so they would be the last two, and thus escape death.

It's not easy to find the surviving positions by analytical means. Instead you should use simulation to find the sequence of eliminations and the position occupied by the last survivor. The program should work for any number of people (n) up to 50 and any skip number k between 1 and n–1

For example, if n = 7 and k = 3, the positions eliminated would be as follows (you might want to trace this on a 7-element circular array of boxes):

Skip positions... Then eliminate position
1 and 2 3
4 and 5 6
7 and 1 2
4 and 5 (plus the eliminated 3 and 6) 7
1 and 4 (plus eliminations) 5
1 and 4 (plus eliminations) 1

Thus the survivor is 4.

The first line of input contains the number of simulations required. Each remaining line contains the simulation parameters n and k for a different simulation. The program's output should just be n, k and the survivor for each simulation. You may assume that n is at least 2 and at most 50, and k is at least 1 and less than n.

### Example

Input:
 ```3 7 3 34 1 4 2 ```

Output:

 ```7 3 4 34 1 34 4 2 1 ```

For 3 bonus marks, show the second-last survivor as well as the last one.

### Test Data

You should test your program on the following data. The last one is the classic Flavius Josephus scenario.

#### Test 1

 ```9 17 11 8 1 5 4 29 2 50 49 18 6 37 3 2 1 41 3 ```

### Marking Scheme

• Correct value for first simulation: 11 marks
• Correct value for remaining simulations: 4 marks
• Displaying the second-last survivor as well as the last: 3 marks

## Task 5. Maximal Subsequence Sum

### Available Marks: 12

This is a classic problem in algorithm design. Maximum marks are given to elegant and efficient solutions.

#### Definitions:

A sequence is a list of values, say numbers, in a fixed order.
A contiguous subsequence is a range of adjacent elements in a sequence.
A subsequence sum is the sum of the elements in a contiguous subsequence.
The maximal subsequence sum is the largest of all possible subsequence sums.

For example, consider this integer sequence:

```3 -4  8  2  0 -1  4 -2  1
```
At first glance the maximal subsequence sum looks like 10 (8 + 2), but if you extend the subsequence forward three more places you get 13 (8 + 2 + 0 + -1 + 4). This is the maximal subsequence sum.

Write a program that accepts an integer sequence and displays the maximal subsequence sum of the sequence. The first line contains the length of the sequence, which is 50 or less. The second line contains the sequence, with elements separated by spaces.

The output should be the sum and exactly how it is formed.

### Example

Input:
 ```9 3 -4 8 2 0 -1 4 -2 1 ```

Output

 ```8 + 2 + 0 + -1 + 4 = 13 ```

### Test Data

You should test your program on the following three files.

#### Test 1

 ```13 5 -9 56 -67 -34 45 -23 89 -78 28 -56 71 -48 ```

#### Test 2

 ```21 1 2 3 4 3 2 1 0 -1 -2 -3 -2 -1 0 1 2 3 2 3 2 1 ```

#### Test 3

 ```31 -3 4 23 6 -5 6 -124 -2 4 0 16 -3 0 -6 15 9 -3 -4 -1 6 0 -3 2 -2 2 -2 -2 2 2 2 -2 ```

### Marking Scheme

• Correct identification of maximal subsequence sum: 6 marks
• Correct sum format: 2 marks
• Quality of algorithm: 4 marks (0 for brute-force, full marks for a linear-time algorithm, part marks for something in between)