Welcome to the UNSW High Schools Programming Competition for 2006.
The Tasks:
Given a list of scores, in order, write a program to generate a rank for each entry. An entry's rank is just its position in the sequence, starting at 1. If there are equal values, however, each of the equal values shares the same rank. This doesn't affect subsequent ranks. For example, here is a list of scores (in descending order) with the corresponding ranks written underneath:
134 109 109 104 94 94 94 67 42 1 2eq 2eq 4 5eq 5eq 5eq 8 9The input format has one score per line. There is no formal limit to the number of values.
You may assume that all numbers are well-formed (legal integer or real format).
100 100 99 98.5 98.4 98.40 98.4 98.399 97.1 92 92 92 92 0.000 0 -1 |
1243 1234 1243 1243 1243 1234 1234 1233 1222 1211 1233 1234 1222 1211 1211 1210 -1 |
To squeeze address information into the phone book Telstra abbreviates suburb names. Vowels carry less information than consonants, especially in the middle of words, so the (simplified) rules for reducing suburb names are
A vowel is defined as one of the 5 letters aeiou. Although 'y' is considered a vowel in certain contexts it is not so here.
Examples:
Suburb | Abbreviation |
---|---|
Banksia | Bnksia |
Little Bay | LttlBy |
Glenorie | Glnrie |
Lane Cove | LnCv |
Illawong | Illwng |
Write a program to abbreviate suburb names this way. Names are provided, one per line. The output should be the original name, one or more spaces, and the abbreviation.
Alexandria Berowra Waters Campsie Doonside East Ryde Fairfield East Granville Heathcote Ingleburn Jannali Kirrawee Lane Cove North Maianbar Neutral Bay Old Toongabbie Parramatta Queenscliff Raby Sans Souci Tempe Ultimo Vaucluse Woolloomooloo Yagoona Zetland |
One of the simplest data compression schemes is called run-length encoding (RLE). RLE replaces a sequence of adjacent equal values with one copy of the value, and a count of the number of times it occurred. This works well for data representing images with regions of uniform colour, for example.
For this exercise we have applied RLE to text input only, and your task is to write the decoder to restore the original data.
An RLE-encoded sequence must be distinguishable from ordinary text. To do so, a special character is reserved to indicate the start of an RLE-encoded sequence. We will use the character '#'. An occurrence of '#' in an encoded file will be legally one of two forms:
#dc ##where d is a digit character ('0' to '9'), representing how many times the character is to be repeated, and c is the repeated character, which can be any printable character, including '#'.
The second kind, "##", represents a single literal '#' character, as a shorter alternative to the encoding "#1#".
If a '#' is followed by other than a digit or another '#', display a question mark '?'.
For example, the input text
ab#3Cde###1Fg#9hhwould be decoded as
abCCCde#Fghhhhhhhhhh
Write a program that reads RLE-encoded data from its input and writes decoded data to its output.
Show your program's output for the following three test files. The last one is long and has lines of up to 55 characters: make sure you transfer it completely to your program. You'll know your program is working if it displays one of the classic ASCII art pictures.
W#1el#1c#1ome#1 t#1o Prog#1co#1m#1p 2#206 |
#4 #3# #2 #2 #2### #3 ###2# #2##9# #####9# #2 #2 #3# #4 #3# #3 ##2#1# >#4>#>#5<#2= e#2ror |
#5 #9 #4X #4 #9 X#4 XX #3 #9 X #3* X#7 #9 #5X #9 X #5* X#3 #9 #3X#5 XX #8 #4X #7* #3X#6 #4X #9 XX #6 XX#3 X #6* #9X#7 #9 #2X #3X #4 XX#6 X #4* X#9 #9 #9 X** X #3 X#8 XX#4 XX#5 X#4 #9 #9 X#3*X X#9 //#4X#7 X#4 #9 #9 #4X X#9 //#3 X #9 #9 #9 XX X#9 //#4 X #9 #9X#9X/ X#5 #3X//#4 X #9 X X#4 X#3 X #3 X #5 X X#4 X#4 X#4 X#5 X X#3 X#4 X#4 X#8 X #9 #9 XX X#4 X#3 X#4 X#8 X#8 #9 #3X XX X#4 #3X#6 X#8 X#6 #9 X X X X X#4 #9 X#9 X#5 #9 XX X #4X #3 X#4 #9 X#9 #8X\#5 XX#3 XX X #4 XX#3 #9 XX#5 #9 X#5 X#4 X XX #6 XX#3 #9 #4X#3 #6X/#5 X#5 #4X #8 #3X#4 #9 XX#3*#9 X#5 X #9 #4X#9X *#3 *#7 X#5 X #6 #9 #9 *#3-* X#5 X#5 X #5 #9 #9 *-* *#3 #3X X#5 X #5 #9 #9 *- *#7 #3X#3 X #4 #9 #9 *- *X #9 #3X #4 #9 #9 *- *X X #9 #3X #3 #9 #9 *- *X#4 X#3 #9 XX #3 #9 #9 *- *XX#4 X#4 #9 X #9 #9 * *X* X#4 X#4 #9 X #9 #9 * *#1X * X#4 X#4 #9 X #9 #9 * * X** X#3 #4X #9 X #9 #9 * * X** XX#5 X #9 X #9 #9 * ** X** X#5 XX #9 X #9 #9 * ** X* #3X#3 X#9 X #8 #9 * **#4 XX#3 #4X#7 #3X #7 #9 * * *#6 #4X#6 X#5 X #6 #9 *#3 * * #9 X#5 X#5 X #7=#7*#3 * * #9 X#5 X#6 #8X\ #8 *#9 * *#6 /#5X#6 #8X\#6 ) #3 #5=*#9* *#5 X#3 #9 #9 ) \ ) #5 #4=*#9 *#5 X#6 #9 \ \#3 )#5X #9=*#9*#7 #4X#9X#9X #2 #9 #9 C#1U#1R#1SE Y#1O#1U, R#1ED B#1A#1R#1O#1N! |
Even if you aren't a football fan you must know the World Cup is on. This task requires you to write a program that assigns points in a tipping competition.
In the competition, each participant (we'll call them a "tipper") predicts the final score for a particular match. A prediction is represented by two non-negative integers: how many goals the first identified team will score, and how many goals the second team will score. When the final score is known, points are awarded to each participant depending on how accurate their prediction was.
The points system varies according to whether or not a draw is predicted (equal number of goals for each side).
Final result | points awarded | |
---|---|---|
Draw occurred | 5 | |
Score was exact | +1 (so total = 6) | |
Draw did not occur | 1 | |
Goal difference is 1 or –1 | +1 (so total = 2) |
The "goal difference" is the difference between the number of goals scored by the first and second team. It's 0 for a draw.
For example, if a tipper predicts 1-1, the following points would be awarded:
Final score | points awarded | |
---|---|---|
1-1 | 6 | |
0-0 | 5 | |
0-1 | 2 | |
4-2 | 1 | |
2-3 | 2 |
Final result | points awarded | |
---|---|---|
Win | 3 | |
Predicted goal difference differs from the actual goal difference by 1 or less | +1 (so total = 4) | |
Predicted goal difference is correct | +1 (so total = 5) | |
Exact score | +1 (so total = 6) | |
Loss | 0 | |
Draw | 0 | |
Draw, but predicted goal difference = 1 or –1 | +1 (so total = 1) |
For example, if a tipper predicts 1-2 the following points would be awarded:
Final score | points awarded | |
---|---|---|
1-2 (correct score) | 6 | |
0-1 (correct goal difference) | 5 | |
2-4 (goal diff incorrect by 1) | 4 | |
0-3 (right team won) | 3 | |
1-0 (wrong team won) | 0 | |
1-1 (draw, 1 pt for goal diff = 1) | 1 |
The output should be the name of each tipper followed by the number of points awarded according to the scoring system described above.
4 3-1 Marcus 1-2 Steve 2-1 Mei-Cheng 3-1 Geoff 2-2 |
7 2-2 Janet 1-0 Jimmy 0-2 Tao 1-1 Alex 4-1 Rui 2-2 Isan 3-4 Keith 0-0 |
10 0-1 Me 0-0 You 0-1 Him 1-0 Her 1-1 Them 1-2 Those 2-1 It 9-9 Another 1-10 Others 3-1 TheRest 99-100 |
Magic squares exist for all orders except 2. For example, an order-3 magic square is shown below. Its row, column and diagonal sum is 15.
8 | 1 | 6 |
3 | 5 | 7 |
4 | 9 | 2 |
For example, the magic square above could be represented as
3 8 1 6 3 5 7 4 9 2 |
You should be able to handle any magic square up to order 9.
The program's output is one of the following statements:
Just as Sudoko puzzles are solved by inferring the contents of empty cells based on the rules of the game, magic squares with missing numbers can be completed using the rules above.
Given an incomplete magic square, with * symbols where the missing numbers are, modify your program to generate the missing values. Only one solution is required in the event that more than one exists.
The input format is the same as above apart from the use of the missing number symbol. If the input contains one or more missing numbers, output the complete magic square. Assume that if the input contains an incomplete magic square none of the error cases will arise.
Judges will be looking very carefully at your program to confirm that it can generate the indicated output. If possible, the code will be compiled and executed. If irregularities are detected, no score is awarded for this task and the team may also be disqualified from the competition.
4 16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1 |
5 1 9 12 20 23 17 25 3 6 14 8 11 19 22 5 24 2 9 13 16 15 18 21 4 7 |
9 9 34 62 12 37 65 24 49 77 15 40 68 27 52 80 3 28 56 21 46 74 6 31 59 18 43 71 35 63 7 38 66 10 50 78 22 41 69 13 53 81 25 29 57 2 47 75 19 32 60 4 44 72 16 61 8 36 64 11 39 76 23 51 67 14 42 79 26 54 55 1 30 73 20 48 58 5 33 70 17 45 |
5 * 7 23 19 * 18 14 * 6 22 10 * 17 13 4 12 3 * 25 * 24 * 11 * 8 |
7 1 8 * 25 35 39 * * 41 44 2 * 17 28 11 21 24 * 37 43 * * * 4 14 * 26 30 20 23 * 40 46 * 10 49 3 13 16 * 34 38 27 * 42 * 5 9 15 |