Welcome to the UNSW High Schools Programming Competition for 2007.
The Tasks:
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 |
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
where abs(x) represents the absolute value of x.
For example, if you use the last ratio above p = 1.6190476, p2 – 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:
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 |
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 |
This is a classic problem in algorithm design. Maximum marks are given to elegant and efficient solutions.
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 |