UNSW High Schools Programming Competition 2010: Open Round
- 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.
- 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: Staircase (easy, 10 marks)
- Vowel Index (easy, 7 marks)
- Climb Analysis (easy to moderate, 9 marks)
- Shoelaces (easy to moderate, 10 marks)
- Code39 Check Symbol (moderate, 13 marks)
- Dominoes (moderate to hard, 21 marks)
Junior Task. Staircases
Available Marks: 10
A certain integer sequence is constructed as follows:
Start with the integer 1. Add 1 to it (giving 2), multiply the result by 1.
Then add 2 to that, multiply by 2, add 3, multiply by 3 and so on.
The sequence thus begins
1 2 2 4 8 11 33 37 148...
Because you use the same factor to add and then multiply before incrementing it,
let's call it the Staircase Sequence.
Write a program to print all values of the Staircase Sequence that are less than a billion
(1,000,000,000 or 109), one per line.
Task 1. Vowel Index
Available Marks: 7
The vowel index of a word is the proportion of vowels among the letters of the word,
rounded to an integer percentage.
For example, the vowel index of "sea"
is 67 and the vowel index of "a" is 100.
Vowels are traditionally the letters a e i o and u.
For the purpose of this exercise, y is also a vowel unless it occurs at
the beginning of a word. Thus "sly" and "yet" both have a vowel index of 33.
Write a program that reads in a number of words, and displays the vowel index
before each of them.
The first line of input is the number of words,
then one word occurs per line.
Words consist only of upper-case and lower-case letters, you can assume there will be no punctuation.
A word can have up to 28 letters, and there can be up to 20 words in the data.
Example
Input:
4
an
Hello
YACHT
yesterday
|
Output:
50 an
40 Hello
20 YACHT
44 yesterday
|
Test Data
You should test your program on the following data.
17
I
audio
antidisestablishmentarianism
wheeeeeeeeeeeeeeeeeeeeeeeeee
diarrhoea
aviation
strengths
progcomp
Progcomp
PROGCOMP
aye
nondeterministically
synonymously
Youthfully
Yellowed
OKAY
AbCdEfGhIjKlMnOpQrStUvWxYz
|
Task 2. Climb Analysis
Available Marks: 9
Bushwalking guides sometimes indicate the difficulty of a track by estimating
the total climb, the sum of all the ascents along the walk.
An ascent occurs when the elevation (height above sea level) increases
over a short section of the track.
Descents are not counted in the total climb.
A related quantity, the total strenous climb, is the sum of all ascents that
are as steep or steeper than 1 in 10, that is, 1m ascent for each 10m of walking distance.
Ascents less than 1:10, and all descents are not counted in the strenuous climb.
The data for your climb analysis program consists of
a number of pairs of numbers, each representing a point on the walk.
The first number of each pair is the distance in kilometres
from the start of the walk,
and the second is elevation of the point in metres.
Each quantity could be an integer or real number, and they are separated by one or more spaces.
The first row of input is the number of data points.
There can be up to 200 data points.
The first data point always has distance 0.0
and distances are strictly increasing (no duplicates).
Write a program that reads the track data,
analyses it and reports two values:
- The total climb of the track; and
- The total strenuous climb of the track,
both expressed in metres.
Example
Input:
8
0.0 500
0.15 510
0.20 520
0.30 470
0.55 540
0.65 540
0.85 550
1.00 535
|
Output:
(Explanation: the ascent from 500m to 510m over 0.15km is 10m in 150m, less than 1:10,
as is the ascent from 540m to 550m. The others are counted as strenuous.
Test Data
You should run your program using the following three data sets.
Test 1
11
0.0 0
1.0 50
2.0 150
3.0 300
4.0 500
5.0 750
6.0 950
7.0 1100
8.0 1200
9.0 1250
10.0 1250
|
|
Test 2
11
0.0 200
0.1 205
0.2 214
0.3 221
0.4 222
0.5 215
0.6 199
0.7 206
0.8 210
0.9 217
1.0 220
|
|
Test 3
134
0.000 1835.0
0.030 1830.8
0.070 1825.1
0.100 1820.9
0.106 1820.0
0.138 1815.0
0.172 1809.7
0.197 1805.8
0.234 1800.0
0.239 1799.2
0.286 1791.5
0.333 1783.8
0.356 1780.0
0.377 1775.9
0.427 1766.2
0.459 1760.0
0.481 1755.3
0.535 1743.7
0.552 1740.0
0.577 1735.5
0.605 1730.5
0.632 1725.7
0.662 1720.4
0.664 1720.0
0.694 1718.6
0.720 1717.5
0.730 1717.0
0.750 1717.8
0.781 1719.1
0.804 1720.0
0.814 1721.8
0.862 1730.2
0.906 1737.9
0.918 1740.0
0.945 1743.8
0.989 1749.9
1.043 1757.4
1.062 1760.0
1.105 1765.9
1.145 1771.3
1.195 1778.1
1.209 1780.0
1.240 1784.0
1.270 1787.9
1.320 1794.3
1.364 1800.0
1.367 1800.2
1.432 1805.4
1.468 1808.3
1.519 1812.4
1.553 1815.1
1.600 1818.8
1.615 1820.0
1.673 1826.0
1.753 1834.2
1.809 1840.0
1.829 1842.5
1.920 1853.8
1.970 1860.0
1.972 1860.1
2.016 1864.7
2.073 1870.6
2.150 1878.5
2.164 1880.0
2.192 1882.5
2.222 1885.4
2.292 1891.9
2.360 1898.3
2.378 1900.0
2.424 1903.3
2.465 1906.2
2.513 1909.6
2.591 1915.2
2.658 1920.0
2.671 1921.0
2.800 1931.3
2.853 1935.5
2.887 1938.2
2.910 1940.0
2.926 1942.2
2.959 1946.8
3.001 1952.6
3.044 1958.6
3.054 1960.0
3.098 1962.9
3.100 1963.0
3.154 1960.0
3.166 1959.2
3.214 1956.1
3.268 1952.5
3.350 1947.1
3.395 1944.1
3.448 1940.7
3.458 1940.0
3.496 1937.0
3.550 1932.8
3.560 1932.0
3.579 1935.1
3.609 1940.0
3.610 1940.3
3.667 1960.0
3.691 1964.1
3.764 1976.7
3.783 1980.0
3.829 1984.1
3.879 1988.6
3.908 1991.2
3.925 1992.8
3.950 1995.0
3.951 1994.9
3.995 1991.2
4.057 1986.0
4.111 1981.5
4.129 1980.0
4.173 1975.0
4.286 1962.2
4.305 1960.0
4.356 1952.8
4.410 1945.1
4.446 1940.0
4.502 1935.0
4.579 1928.0
4.634 1923.1
4.668 1920.0
4.685 1918.4
4.737 1913.6
4.782 1909.5
4.836 1904.5
4.875 1900.9
4.885 1900.0
4.920 1897.2
4.963 1893.8
4.991 1891.6
5.019 1889.4
|
|
Test 3 data plotted as a walk profile:
Marking Scheme
- Total climb: 5 marks
- Total strenuous climb: 4 marks
Task 3. Shoelaces
Available Marks: 10
There is a remarkably elegant method of calculating the area of a
(non self-intersecting) polygon
given the x and y
coordinates of each vertex.
It was devised by the great mathematician Carl Friedrich Gauss (1777–1855),
and is formally known as the Gauss-Green formula
but is more colourfully called the Shoelace Formula.
Consider this quadrilateral, whose area is 10.5 square units:
The method, illustrated by the diagram at right, is as follows:
- Write down the coordinates in either clockwise or anticlockwise order,
repeating the starting coordinates at the end.
- Draw a blue line from each X value to the Y value in the row below,
and a red line from each Y value to the X value in the row below.
- Multiply each pair of numbers with a line between them.
Subtract the sum of the red products from the sum of the blue products.
-
The absolute value of half the difference gives the area of the polygon.
The crossed lines look like shoelaces, hence the name of the method.
For the example above, the sum of the blue products is
3×1 + 5×2 + –1×4 + 0.5×4 = 11
while the red sum of the products is
4×5 + 1×–1 + 2×0.5 + 4×3 = 32
and the area is the absolute value of (11–32)/2 = 10.5.
Write a program that reads in up to 100 coordinate pairs representing the vertices of a polygon,
and calculates the area using the shoelace formula.
The first line of input is the number of points following,
and the last point is always the same as the first.
Each line has one X and one Y value, are separated by one or more spaces.
Example
Input:
Output:
Test Data
You should test your program on the following three sets of data.
Test 1 (rotated square)
5
0 0
8.1915204428899178968448838591684 5.7357643635104609610803191282616
2.4557560793794569357645647309069 13.92728480640037885792520298743
-5.7357643635104609610803191282616 8.1915204428899178968448838591684
0 0
|
Test 2 (star, centred on the origin)
33
0 128
19 97
50 120
53 82
91 91
80 53
120 50
97 19
128 0
97 -19
120 -50
80 -53
91 -91
53 -82
50 -120
19 -97
0 -128
-19 -97
-50 -120
-53 -82
-91 -91
-80 -53
-120 -50
-97 -19
-128 0
-97 19
-120 50
-80 53
-91 91
-53 82
-50 120
-19 97
0 128
|
|
Test 3 (UNSW campus outline)
15
336072.0 6245377.0
336025.0 6245608.0
335968.0 6245862.0
336180.0 6245828.0
336782.0 6245745.0
336798.0 6245735.0
336824.0 6245728.0
336957.0 6245697.0
336938.0 6245553.0
336922.0 6245428.0
336570.0 6245497.0
336536.0 6245296.0
336525.0 6245295.0
336370.0 6245329.0
336072.0 6245377.0
|
These are grid coordinates expressed in metres.
The Kensington campus has an area between 30 and 40ha
(there are 104 square metres in a hectare).
|
Task 4. Code39 Check Symbol
Available Marks: 13
Unique identifiers such as part numbers are recorded
in machine-readable form using bar codes.
A popular bar code system is called code39 or code 3-of-9,
the numbers relating to the different kinds of individual bars.
The identifier to be encoded is an alphanumeric string of any fixed length
of up to 35 characters, using characters selected from
the 10 digits and 26 upper case letters.
To guard against errors, especially when typed by hand,
it is common to append a check symbol (digit or letter) to the identifier
before creating the bar code.
The check symbol is calculated using this algorithm:
-
Write out the identifier. Convert each symbol to its value,
by assigning digits their usual value and A=10, B=11, ..., Z=35.
-
From the right, assign increasing weights to each character position,
so the right-hand symbol is worth 1, the one next to it is worth 2, and so on.
-
Multiply each symbol value by the weight and add up the products.
-
Calculate the remainder when the sum is divided by 36.
The is the check value.
-
Convert the check value to a symbol by the reverse mapping used in step 1.
For example, for the code pictured, the algorithm is as follows:
Symbol 24 is the letter O (10 is A, and O is 14 places further on)
so the full code is ABCD456O.
To determine whether a suspect code is valid, you strip the check symbol,
and apply the algorithm to the rest of the code to see what it should be.
For example, if someone accidentally swapped the 4 and the 5 (a common mistake),
the check symbol for the identifier ABCD546 is P rather than O.
Write a program that can validate codes and generate codes from identifiers.
Each line begins with the letter G or V followed by a space
and an alpanumeric string.
-
If the key letter is G, the program should generate a code from
the identifier that follows, and display the code.
-
If the key letter is V, the program should display the code that follows,
and either Valid or Invalid, according to whether the code is valid.
The first line contains the number of strings to be processed
(a maximum of 25).
Each string will be no longer than 36 characters.
Example
Input:
5
G ABCD456
V ABCD546P
G 9329538001220
G UNSWPROGCOMP2010
V TESTING
|
Output:
ABCD456O
ABCD546P Valid
93295380012208
UNSWPROGCOMP2010D
TESTING Invalid |
(The third one is a numeric identifier that also produces a numeric check symbol,
part marks are awarded if your program only works for purely numeric codes).
Test Data
You should test your program on the following data.
24
G 9
G 834209505
G 788728372837289357289357275
G 00000001
G 10000000
V 999
V 0009389471238872847
V 23857298357239
V 34905390483956
G X
G PART378954
G 187U587
G 1A1A1A1A1A1A1A1A1A1A1A1A1A1
G 234234232304
G ABCDEFGHIJKLMNOPQRSTUVWXYZ
G ABCDEFGHIJKLMNOPQRSTUVWXYZ987654321
G TASK4
G CATCH22
G QQQQQQQQQQQQQ
V ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789L
V 2010PROGCOMP8
V 2010PROGCOMPS
V QQ
V HELLOWORLD
|
Marking Scheme
- Correct generation of purely numeric codes only: 4 marks
- Correct generation of full alphanumeric codes: 6 marks
- Correct validation: 3 marks
Task 5. Dominoes
Available Marks: 21
Dominoes are rectangular tiles, each containing a pair of integers
that range from 0 to 6, represented by a number of dots.
Every combination occurs exactly once in a full set.
Each member of the pair is associated with a particular end of the domino.
Two dominoes can be placed end-to-end only if the number at the touching end
on each domino is the same. Several dominoes may be placed end-to-end provided this
rule applies to each junction.
Such an arrangement is called an alignment.
Your program must read input describing a number of different domino configurations,
preceded by the number of configurations.
Each configuration is on a separate line, and
consists of the number of dominos, followed by the list of dominos,
each represented by a pair of digits separated by a colon (:).
There is one space between dominoes.
For each configuration your program should produce one of the following
sets of output. The number of marks awarded depends on the complexity of the analysis.
-
If the dominoes can be laid end-to-end in exactly the order given,
display the alignment on a single line, preceded by the word "Aligned: ".
Marks: 5
-
If the dominoes can be laid end-to-end but only by reversing one or more
of the dominoes and retaining the domino order,
display the adjusted alignment on a single line preceded by the word "Flipped: ".
Marks: 7
-
If If the dominoes can be laid end-to-end but only by re-ordering
and possibly reversing some of the dominoes,
display the adjusted alignment on a single line preceded by the word "Shuffled: ".
There may be more than one legal alignment, any will do.
Marks: 9
-
Any any other case display the phrase "No alignment possible".
Example
Input:
4
6 3:3 3:2 2:2 2:4 4:0 0:1
5 4:3 5:4 5:6 1:6 1:1
3 1:2 2:5 3:4
7 6:5 6:6 0:4 4:1 5:4 2:6 4:2
|
Output:
Aligned: 3:3 3:2 2:2 2:4 4:0 0:1
Flipped: 3:4 4:5 5:6 6:1 1:1
No alignment possible
Shuffled: 0:4 4:5 5:6 6:6 6:2 2:4 4:1 |
Test Data
You should test your program on the following data.
11
1 6:6
2 1:2 2:5
8 3:4 5:3 6:5 6:6 0:6 4:0 5:4 5:5
3 5:6 6:6 3:4
3 2:4 3:4 3:2
28 0:2 2:4 4:6 6:3 3:5 5:2 2:6 6:1 1:4 4:0 0:5 5:1 1:3 3:0 0:6 6:6 6:5 5:5 5:4 4:4 4:3 3:3 3:2 2:2 2:1 1:1 1:0 0:0
28 6:6 6:5 6:4 6:3 6:2 6:1 6:0 5:5 5:4 5:3 5:2 5:1 5:0 4:4 4:3 4:2 4:1 4:0 3:3 3:2 3:1 3:0 2:2 2:1 2:0 1:1 1:0 0:0
20 6:5 5:4 4:3 3:2 2:1 1:0 0:2 2:4 4:6 6:3 3:5 5:2 2:6 6:1 4:0 0:5 5:1 1:3 3:0 0:6
6 4:3 5:2 1:6 0:5 2:3 6:4
8 0:0 1:0 1:2 3:2 3:4 5:4 5:6 6:6
6 3:5 0:0 6:0 2:4 4:4 4:3 |
|