The Tasks:
Junior task: Team Count (easy, 10 marks)
The Progcomp 2011 rules state:
In addition to any number of teams of three,
each high school will be allowed to register exactly ONE or TWO teams of 2 students.
A high school with a single outstanding student may register a team consisting only of that student, but only if no other team is registered
from that school.
Write a program that, given the number of participants a school has (1 or more), determines exactly how many teams of 3, teams of 2 and teams of 1 the school is allowed to register.
The first line of input to the program is the number of schools, followed by the number of participants for each school, each on a separate line. No other information is provided or needed.
The program should show the number of participants and how many teams of each size, using singular or plural terms as appropriate ("team" vs "teams"), and omitting mention of zero cases. Use the format shown below, including a comma to separate items and a full stop at the end. Marks are awarded both for computational correctness and following the format.
4 7 9 2 1 |
Output:
7 participants = 1 team of 3, 2 teams of 2. 9 participants = 3 teams of 3. 2 participants = 1 team of 2. 1 participant = 1 team of 1. |
9 3 22 1 8 120 121 4 5 2 |
A chronogram is a phrase in Latin or another language, that embeds a date in roman numerals. To decode it, extract each roman numeral (capital letters only) and add up their face value, regardless of the order in which they occur. For example, "My Day Closed Is In Immortality" (commemorating the death of Elizabeth I in 1603) contains the roman numerals MDCIII, which is 1000 + 500 + 100 + 1 + 1 + 1 = 1603. In this case the order is preserved (a natural chronogram), but this is not essential.
Roman numerals and their values are shown in the table below.
M = 1000 D = 500 C = 100 L = 50 X = 10 V = 5 I = 1
Write a program that reads a number of phrases and calculates the chronogram value for each one. The first line of input indicates the number of phrases, each of which can have up to 150 characters, followed by the phrases, one per line.
For each phrase your program should display the chronogram value followed by the phrase.
6 SAVVY PROGRAMMERS VEX CHURLISH TESTERS some roman numerals but they're in the wrong case, except thIs one. FIRE STARTS IN THE KING'S BAKERY, THEN LONDON IS BVRNING, CONSVMEd BY THE INFERNO. note the sneaky olde-style use of V instead of U in the previous example My Mother Plays the Xylophone Intently EXPECT THE DEVIL |
Output:
2176 SAVVY PROGRAMMERS VEX CHURLISH TESTERS 1 some roman numerals but they're in the wrong case, except thIs one. 1666 FIRE STARTS IN THE KING'S BAKERY, THEN LONDON IS BVRNING, CONSVMEd BY THE INFERNO. 5 note the sneaky olde-style use of V instead of U in the previous example 2011 My Mother Plays the Xylophone Intently 666 EXPECT THE DEVIL |
12 AFTER A LONG, PERILOVS JOVRNEY, COLVMBVS EXVLTANTLY SHOWS THE WAY TO AN VNKNOWN CONTINENT. MICHELANGELO, SCVLPTOR / PAINTER STARTS TO PAINT THE CHAPEL ROOF. INTERESTING DISCOVERY FOR COOK, NAVIGATOR IN THE ENDEAVOUR: THE GREAT SOUTHERN LAND. THE FIRST FLEET (SIX CONVICT TRANSPORTS, THREE STORE SHIPS + TWO NAVAL ESCORTS) ARRIVES AT SYDNEY COVE, LED BY CAPTAIN ARTHUR PHILLIP. ALEXANDER GRAHAM BELL CAN VERIFY INVENTION OF THE INITIAL TELEPHONE. INTERNATIONAL CONTESTS BETWEEN ATHLETES ARE HELD AT ATHENS: A WAY OF REVIVING ANCIENT WARRIOR GAMES, OR A VERY EXHAUSTING EXHIBITION OF FITNESS? TITANIC MAKES DISASTROVS COLLISION WITH AN ICEBERG. VENTURE TO CELEBRATE LUNAR EXCURSION: A GIGANTIC LEAP FOR MANKIND. More tests, including case sensitIVITY USING AXES, LUMBERJACKS VERY QUICKLY FELLED THE WIZARD'S PINE FOREST (quick brown fox analogy) CDs versus DVDs nothing |
Write a program that, given the lengths of the sides of a triangle, does the following:
A neat summary of the 7 possible triangle types is this diagram, first published in 1901 (there aren't 9 types because equilateral triangles can only be acute):
Wentworth and Hill (1901), First Steps in Geometry.
Heron's formula calculates the area A using the lengths of the sides a, b, c:
where the semiperimeter s is given byIf a is the longest side, then the largest angle α opposite it can be calculated from the cosine rule:
Should you need to know, π is approximately 3.141592653589793238462643383279502884197169399375105820974944592307816406286… ☺
For the purposes of this task, if the difference between two quantities is less than 10–8 in absolute value they are considered to be equal.
Each line of input after the first consists of three real numbers, representing the sides of a (possible) triangle, separated by spaces. The first line contains the number of triangles to be classified (up to 20).
Your program should display the three sides, then either the phrase "is not a triangle" or the above classification (both words, such as "scalene & right-angled") followed by the calculated area in any convenient format. Don't show the area if it isn't a triangle.
4 3 5 4 10 67 13 1.5 1.5 1.5 4.78 9.6321 5.043 |
Output:
3 5 4 is scalene & right-angled. Area = 6 10 67 13 is not a triangle. 1.5 1.5 1.5 is equilateral & acute. Area = 0.974278579 4.78 9.6321 5.043 is scalene & obtuse. Area = 4.63893981 |
5 marks for the classification and 4 for areas.
11 2 3 2 1 2 3.000001 10.000000001 10.000000004 9.999999999 -4 4 4 123.5 200 167.2 4 1 4.123105625 30 15 16 11.5 11.5 16 5 0 8 5.7 8.0610173 5.7 999 99 9 |
In the game of darts each player throws up to three darts at a time onto the dartboard, scoring points for hitting various regions of the board. The aim is to count down from a starting value (usually 501 points), reaching exactly zero. Players alternate with three darts each.
Region | Effect on Score | Notation |
Single score sectors | Score the sector value | SN |
Outer (double) ring | Score double the sector value | DN |
Inner (triple) ring | Score triple the sector value | TN |
Outer bullseye | Score 25 points | OB |
Inner bullseye | Score 50 points | IB |
For example, if three darts are scored as D20, OB and T7 the total score would be 2*20 + 25 + 3*7 = 86 (this is not the optimal way to reach 86, however).
Write a program that can determine what scores a player should aim for for each of their darts in order to reach a specified target score exactly. If there is no possible way of reaching the target score then a combination of darts that gets closest to the score without exceeding it should be generated. Scores should be in decreasing order of value, and solutions don't have to use all three darts.
The input file has a score (a positive integer) on each line, with the first line giving the number of scores to be processed (up to 30). The program should display the target score, a : symbol, up to three scores separated by + symbols, an = and what they add up to.
As well as producing a solution that adds up to the appropriate score, to maximise the available marks your program must follow these rules:
You might find this task easier if you first systematically generate a table containing all 180 different solutions.
5 15 34 79 1 200 |
Output:
15: S15 = 15 34: D17 = 34 79: T20 + S19 = 79 1: S1 = 1 200: T20 + T20 + T20 = 180 |
23 5 8 18 21 25 28 31 44 83 85 93 101 103 120 141 145 150 161 163 176 177 180 501 |
An old, though seriously defective, way of generating pseudo-random numbers (apparently random but determined by an algorithm) is the so-called Mid Square Method. Although it works for various lengths, for this task we are restricting it to numbers with 5 decimal digits (including the digit 0).
Take a 5-digit integer. This is called the seed for the sequence. Square it, if necessary padding the result on the left with zeroes to make exactly 10 digits. Extract the middle 5 digits from the result (actually drop the first 2 digits and extract the next 5, as 10 digits doesn't have a unique middle). This number is the next one in the sequence. Repeat as many times as desired.
Implementation note: 10 decimal digits requires 34 bits to represent: if you have a choice of types you may wish to do your calculations using double precision floating point.
Definitions:
The problem with the method is that the sequence eventually, and sometimes quickly, ends up in a short cycle. For example, if a sequence reaches 00000 the next number is also 00000 and so on. If the seed is 64493 its square is 4159347049, so the sequence goes
64493 59347 22066 86908 53000 09000 81000 61000 21000 41000The next number is 81000, so this sequence, of length 10, ends in a cycle of length 4 (bold).
Write a program that generates mid-square 5-digit sequences. Use it, along with any filtering or analysis tools you happen to have available (or can write quickly) to answer the following seven questions (2 marks each):
Charles Babbage, computing pioneer, is credited with the game of word squares, where n n-letter words are arranged in a grid so that they read the same from left to right and from top to bottom. The following are examples of word squares:
T O E B A B Y F R I L L R E A C T S O N E A R E A R O D E O E X P O R T E E L B E E R I D E A S A P P E A R Y A R D L E A P S C O E R C E L O S S Y T R A C T S S T R E S S
Write a program that can generate word squares from a list of words in upper case, all of the same length (at least 3 and no more than 6). For full marks you will have to produce a single word square, one that uses the largest number of different letters of all word squares obtained from the word list. If there are multiple word squares with the same number of different letters, any one will do.
Input to the program is just a list of words. If there is no solution, the program must state this, otherwise it should display the selected solution in the format shown in examples. Two of the data files are fairly long, and are provided as links rather than shown on this page.
LAST OPUS CATS DOGS POST STOP NEXT PIGS TYPO COWS |
Output (this uses just 6 different letters but is the only solution):
S T O P T Y P O O P U S P O S T |
Test 1 (15 words) | Test 2 (66 words) | Test 3 (3138 words) |
---|---|---|
JIG WIN PUN AGE ICE LAD SEA SAG POD EGG GNU FLY TIN ART YES |
Unix line terminators Windows line terminators |
Unix line terminators Windows line terminators |