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!

The Tasks:

- Time Flies Like an Arrow (easy, 12 marks)
- Golden Ratio (easy to moderate, 8 marks)
- Index Generator (easy, 10 marks)
- Josephus Problem (moderate, 18 marks)
- Maximal Subsequence Sum (moderate to hard, 12 marks)

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.

4 0509 1685 2933 2259 |

Output:

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

6 0138 0700 1001 1234 1333 2345 |

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

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

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

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(*p*^{2} – *p* – 1) < 10^{–14}

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

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

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

- The value of
*p*, to at least 12 decimal places - The value of
*p*^{2}–*p*– 1 - The Fibonacci pair (both numbers) whose ratio is
*p*

Use double-precision real arithmetic if possible.

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.

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 |

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

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

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

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*.

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.

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

- 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

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

A

A

The

For example, consider this integer sequence:

3 -4 8 2 0 -1 4 -2 1At 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.

9 3 -4 8 2 0 -1 4 -2 1 |

Output

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

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

21 1 2 3 4 3 2 1 0 -1 -2 -3 -2 -1 0 1 2 3 2 3 2 1 |

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 |

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