Welcome to the UNSW High Schools Programming Competition for 2009.

- 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.
- A senior team may attempt the Junior task, but it will be marked
*only*if they submit attempted solutions for no more than two other tasks. - 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, unless otherwise explicitly stated. Hand-crafted output will result in the team's disqualification. - Good luck and have fun!

The Tasks:

Junior task: Two-Up (easy, 10 marks)

- Digital Extraction (easy, 7 marks)
- Title Case (easy to moderate, 9 marks)
- Day of the Week (easy to moderate, 10 marks)
- Product Codes (easy to moderate, 13 marks)
- Trampolines (moderate to hard, 21 marks)

The traditional Australian gambling game of two-up can legally be played only on Anzac Day each year. Its rules are simple, especially in the limited form described here. One person, the Spinner, bets Heads (H) or Tails (T). He or she then throws two pennies up in the air. If the pennies land with one head showing and one tail showing, the result is called ODDS and the Spinner throws again. Otherwise the Spinner wins if the pennies (now both Heads or both Tails) match the bet they made, and loses otherwise.

If five ODDS are thrown in a row, the Spinner loses too.

Write a program that scores this version of two-up. The input consists of several lines, each representing a throw, preceded by the number of throws. Each throw consists of a bet (H or T) followed by the result of the throw (two symbols, each H or T). The three letters are separated by a space.

The program should repeat the input and show the result of the throw on the same line. The result can be WIN, LOSE, ODDS or LOSE: 5 ODDS.

9 T T H T T T H T T H T H H H T H H T H T H H T H T H H |

Output:

T T H ODDS T T T WIN H T T LOSE H T H ODDS H H T ODDS H H T ODDS H T H ODDS H T H LOSE: 5 ODDS T H H LOSE |

You can assume each line of input is a valid throw. Bets will only change after a win or loss.

16 H H T H T H H H H H T T T H T T H T T T H T H T T T H T T T H T H H T H H H T H H T H T T T H H |

- Normal WIN/LOSE/ODDS decision: 7 marks
- Correct 5 ODDS decision: 3 marks

I bet you get annoyed at websites that refuse to accept a credit card number, account number or phone number that contains spaces or hyphens, even though these separators make it easier to remember and accurately type the value.

Write a program that is smart enough to ignore all the non-digits in a string, displaying only the digits. If there are no digits, say so.

Your program should be able to process many sets of data, though you will get some marks if it correctly handles the first one. The first row of input is the number of strings, followed by one string per line. There may be as many as 20 strings and each string may be up to 60 characters long. Each line of output should consist of the input string, an equals sign and the extracted digits (or the "no digits" message if applicable).

4 123 456 [7854-8954-8942] #!)A*%#O&*&% (02) 9900-6795 |

Output:

123 456=123456 [7854-8954-8942]=785489548942 #!)A*%#O&*&%=no digits (02) 9900-6795=0299006795 |

10 78-3044/ 2678543 123456789 no.666<<< 00489;78954.22 ------4------ l33t n00b twenty-seven 809582098350298902l8450230958098223422393850298059809243O52. he110 sa1l0r |

- Correct answer for one case: 4 marks
- Correct answer for all valid cases: 2 marks
- Correct identification of no-digit cases: 1 mark

A string written in *title case* has __E__very __W__ord __C__apitalised
(except sometimes for trivial ones).
Phrases that name things, like people, places and creative works are usually written in title case.
This task comes in two versions, a basic one and a more difficult but improved version.

Write a program that reads in strings, one per line,
and displays each string with title case,
except that existing capital letters are retained
(for example, to stop **NSW** becoming **Nsw**).
A word is defined as a sequence of letters surrounded by non-letters
or the start or end of the string.
All characters are normal printable text characters (7-bit ASCII).

*Hint:* A lower case letter should be converted to the corresponding upper case letter
only when preceded by a non-letter or the start of the string.
Every other character is unchanged.

The input is preceded by a line indicating the number of strings to be converted. Each string is a maximum of 60 characters long.

5 the cat sat on the mat the university of new south wales, sydney NSW 2052 2001, a space odyssey (Stanley Kubrick, 1968) o'dwyer, fleetwood-smith and d'silva "a clockwork orange (stanley kubrick, 1970)" |

Output:

The Cat Sat On The Mat The University Of New South Wales, Sydney NSW 2052 2001, A Space Odyssey (Stanley Kubrick, 1968) O'Dwyer, Fleetwood-Smith And D'Silva "A Clockwork Orange (Stanley Kubrick, 1970)" |

To get full marks, your program should also accept a "stop list" of words, one per line, that are only capitalised if they are the first word in the string. Stop words are in lower case, and only match words completely in lower case. The first line of input will have two numbers, the first is the number of stop words and the second is the number of strings. Then follows the stop words (in alphabetic order) and the strings to be converted.

3 2 a on the the cat sat on the mat "mutiny on the bounty" |

Output:

The Cat Sat on the Mat "Mutiny on the Bounty" |

9 pack my box with five dozen liquor jugs cigar? toss it in a can, it is so tragic (palindrome) it's a mad mad mad mad world a 20th century frog new york, NY, USA [{!@#$%^&*(x)_+-=:";'y,.z/?~`|}] 1234567890 abc.Abc.ABc.ABC.aBC.aBc |

36 12 a am an and as at be but by do for from had has have if in into is it its of on or s so t th than that the this to was what with a few rolling stones' songs: you can't always get what you want (here comes your) 19th nervous breakdown ain't too proud to beg live with me ALL CAPITAL LETTERS a "Title Case" title no pet so tragic as a cigar to step on (another palindrome) a man, a plan, a canal: Panama! (yet another palindrome) full circle, a TV series presented by michael palin-drome (sorry) ###a###a###a### was.was.Was.WAs.WAS.wAS.wAs |

- Basic version: 5 marks
- Improved version: 4 marks

One of the peculiarities of the calendar is that the day of the week for any date since 15 October 1582 can be determined using only a few steps of arithmetic. The formula devised by Christian Zeller (1822-1899) is known as Zeller's Congruence. One form of the formula is

w = (d + [2.6m – 0.2] + Y + [Y/4] + 5C + [C/4] ) mod 7 |

*w*is the calculated day of the week, counting from Sunday = 0, Monday = 1, etc;*d*is the day of the month;*m*is the month number, starting with March = 1, April = 2, etc. January and February are counted as months 11 and 12 of the*previous*year;*Y*is the last two digits of the year; and*C*is the first two digits of the year.

Values inside square brackets [...] are truncated to integer,
and **mod** is the modulus
or remainder operator.

For example, [3.75] = 3, [11] = 11,
9 **mod** 7 = 2
and 42 **mod** 7 = 0.

Example: Australia Day this year, 2009-01-26. Here
*d* = 26, *m* = 11, *Y* = 8, *C* = 20
(use previous year for Jan/Feb, in this case 2008).
Calculate

w = (26 + [2.6×11 – 0.2] + 8 + [2] + 5×20 + [5]) mod 7= (26 + [28.4] + 8 + 2 + 100 + 5) mod 7 = 1 |

Write a program that reads any number of dates, calculates the day of the week for each using
Zeller's Congruence and displays its name.
Dates are in ISO 8601 format (yyyy-mm-dd).
Part marks will be given for correctly calculating the day of the week
for the first test date given below, regardless of how you enter
the date into the program.
If your programming language provides calendar functions you may only
use them for validating dates, *not* for the day-of-the-week calculations.

For full marks you will need to identify invalid dates such as 2009-06-31, but you may assume that the input consists of three non-negative integers separated by hyphens and the year is valid.

The first line of input contains the number of dates. There may be up to 20 dates.

4 2009-06-12 1792-02-29 1992-09-31 2001-09-11 |

Output:

2009-06-12 is a Friday 1792-02-29 is a Wednesday 1992-09-31 is not a valid date 2001-09-11 is a Tuesday |

13 1945-08-15 2009-12-31 2010-01-01 1582-10-15 2008-02-28 1770-05-29 2009-02-29 1861-07-14 1855-12-03 2100-02-29 1616-04-23 2050-03-31 2009-13-13 |

- Correct day of the week for the first set of data: 5 marks
- Correct values for other valid cases: 3 marks
- Correctly identifying invalid dates: 2 marks

The sum of the digits in odd positions, plus three times the sum of the digits in even positions, is a multiple of 10. |

A consequence of the rule is that mis-typing a single digit, or (with a few exceptions) swapping adjacent digits of a valid code always produces an invalid code, so these kinds of error can be detected.

For example, the validity of the code pictured is demonstrated by this diagram:

Write a program that reads what are supposed to be product codes, one per line, and responds with a copy of the input, a space and either

- an error message "has the wrong length" if the input is less than 12 or more than 13 digits long (2 marks)
- the phrase "is valid" or "is INVALID" if the input is 13 digits long, according to whether the code satisfies the validation rule (7 marks), and
- the phrase "full code is " followed by the completed code that starts with the input, if the input has exactly 12 digits (4 marks)

6 9780091835132 9780091853132 9780031835132 978009183513 97800918351 97800918351399 |

Output:

9780091835132 is valid 9780091853132 is INVALID 9780031835132 is INVALID 978009183513 full code is 9780091835132 97800918351 has the wrong length 97800918351399 has the wrong length |

(The first invalid code swapped the adjacent 3 and 5, while the second replaced the second 9 by a 3.)

17 9312650441905 9300643881051 9329538001220 8850539180252 9781864364386 4902030309351 8373610005133 0123456789876 1234567898765 930064838101 978086840862 400638133363 978097511941 12345678901234 98765432109 9876543210 9 |

- Correct identification of invalid lengths: 2 marks
- Correct identification of valid and invalid codes: 7 marks
- Correct generation of full code from 12-digit prefix: 4 marks

You have climbed through the corner window of a rectangular room
filled with trampolines in a fixed grid.
The trampolines have varying elasticity, and can propel you
an integer number of positions horizontally or vertically.
Starting at the top left corner (shown in yellow in the example),
you want to reach the exit
at the bottom right corner (the green square labelled 0)
with the smallest number of jumps.

You must follow these rules:

- You must jump exactly the number of squares indicated by the elasticity of the trampoline you just jumped on.
- You can't jump diagonally.
- You can't bounce off a wall or jump out of the room.
- You can only jump on each trampoline at most once.

We refer to trampoline positions as *row*:*column*,
with rows and columns counting from 1.
Starting at 1:1, there are 5 different paths through the sample room,
the shortest requiring 5 jumps:

1:1 1:2 1:3 3:3 3:1 3:4 1:1 2:1 2:3 3:3 3:1 3:4 1:1 2:1 2:3 1:3 3:3 3:1 3:4 1:1 1:2 2:2 2:4 2:1 2:3 3:3 3:1 3:4 1:1 1:2 2:2 2:4 2:1 2:3 1:3 3:3 3:1 3:4

Write a program that reads the layout of a room and displays one or more paths from 1:1 to the exit, one per line in the format above. For full marks the program's output should be

- The number of valid paths
- The length of the optimal (shortest) path(s)
- All optimal paths

The input consists of a line containing the number of rows and columns separated by a space, then the elasticity of the trampolines in each row, one row per line, with one space between each cell value (trampoline elasticity). The room has a maximum of 8 rows and 8 columns. Elasticity values are positive integers less than the longer dimension of the room (so they are never more than 7). The exit square is always the last cell in the last row, and has value 0.

Sample data:

3 4 1 1 2 1 2 2 1 3 3 1 2 0 |

3 3 1 2 1 2 1 2 2 1 0 |

4 5 3 4 2 3 2 2 1 3 2 1 1 3 2 1 4 2 3 1 2 0 |

8 8 2 4 2 4 1 3 2 6 1 3 5 2 4 3 6 1 6 5 1 7 4 6 4 2 7 3 2 5 3 1 7 1 2 7 6 2 3 4 3 6 3 3 3 3 3 3 3 3 7 4 3 2 1 4 4 5 1 1 4 3 3 2 1 0 |

- Finding any valid path in Tests 1 and 2: 8 marks
- Finding all valid paths in Tests 1 and 2: 4 marks
- Identifying one of the optimal (shortest) paths on Tests 1 and 2: 3 marks
- Correctly counting the number of paths in Test 3 using any tool you like: 3 marks
- Program counts solutions and shows only and
*all*optimal paths for all three tests: 3 marks