TUDPC 2004
The Problems

- Main page
- Contest 2008
- Contest 2006
- Contest 2005
- Rules
- Refefree
- Tutorials
- Training
- Archive
- Contact & Staff

- Forum...

On this page the background for every problem is given. More information about the problems can be found in the problemset. At the end you see a summary of the results achieved by the participating teams.

# 1 Castle Walls

In medieval times, knights commanded big armies of peasants. When they had to storm a castle they would
line up neatly in front of the castle’s wall and throw their grappling hooks over the walls. If one does not
throw straight it can easily happen that two hooks cross, making it impossible for the two peasants to climb
the wall. That’s why every knight made his peasants practice a lot so that this would not happen in combat.
Due to the recent Sir Arthur-Madam Claire Marriage (ACM), two peasant armies have to be merged.
Traditionally Sir Arthur’s peasants wear blue and Madame Claire’s peasants wear red. When practicing
together, both armies mix up in front of a castle’s wall. On Sir Arthur’s command, they all throw their
grappling hooks. Due to their perfect training the hooks will never cross within an army, however it can
happen that a hook thrown by a blue peasant crosses one thrown by a peasant of the red army.
For statistical purposes, Sir Arthur now needs to find out how many grappling hooks have crossed so
that he can measure how well their armies have already been merged.

# 2 DNA Laboratory

Having started to build his own DNA lab just recently, the evil doctor Frankenstein is not quite up to date
yet. He wants to extract his DNA, enhance it somewhat and clone himself. He has already figured out how to
extract DNA from some of his blood cells, but unfortunately reading off the DNA sequence means breaking
the DNA into a number of short pieces and analyzing those first. Frankenstein has not quite understood how
to put the pieces together to recover the original sequence.
His pragmatic approach to the problem is to sneak into university and to kidnap a number of smart
looking students. Not surprisingly, you are one of them, so you would better come up with a solution pretty
fast.

# 3 Extra Terrestrial PISA Test

On the planet Divido teachers have a serious problem. Due to the spread of calculators the students cannot
do long division with pencil and paper any longer. But now the planetarian government has announced a
test for all students in basic schools to test their math skills. Because it has to be a multiple choice test the
students only have to calculate the length of the period when dividing two numbers. Your task is to write
a program which calculates the right solutions in advance to ease the correction of the test. An additional
problem occurs because not all intelligent species on Divido have the same number of fingers and thus their
systems of numbers have different bases.

# 4 Heavy Transportation

Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he
needs a clever man who tells him whether there really is a way from the place his customer has build his
giant steel crane to the place where it is needed on which all streets can carry the weight.
Fortunately he already has a plan of the city with all streets and bridges and all the allowed weights.
Unfortunately he has no idea how to find the the maximum weight capacity in order to tell his customer
how heavy the crane may become. But you surely know.

# 5 Dory’s Phonebook

Dory suffers from short term memory loss. Telephone numbers are one of the greatest mysteries to her.
Whenever she wants to call her friend Marlin she discovers that she can hardly remember his name. Because
words are not that hard (she can even speak foreign languages) we should help her in translating phone
numbers to words.
We want to use a mapping for encoding telephone numbers by words, so that it becomes easier to
remember the numbers.

# 6 Yeehaa!

George B. wants to be more than just a good American. He wants to make his daddy proud and become a
western hero. You know, like John Wayne.
But sneaky as he is, he wants a special revolver that will allow him to shoot more often than just the
usual six times. This way he can fool and kill the enemy easily (at least that’s what he thinks).

# 7 Magic Trick

Warning! This problem statement contains a serious spoiler. It shows the trick behind a magic trick. So
if you still want to be amazed in case somebody shows this trick to you then do NOT read the rest of this
problem statement. Stop reading... NOW!

# 8 Formula Racing

The brand new formula racing team Irarref needs your help! Irarref doesn’t have any real good drivers but
they want to dominate formula racing. Since fairness doesn’t mean anything to them they are trying to build
a fully automatic driving control which needs almost no driver interaction.
Before actually trying the automatic driving control on track and risking to crash their precious cars
(they don’t care much about their drivers), they want to test it in a computer simulation.

# Results

The first numbers shows the number of submissions, the second the points received. The total column sums up the submissions and shows the number of solved problems.

Team | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Total
Heart Coders |  |  |  |  |  | 1/88 | 2/-- | 1/-- | 4/1
iguvi | 2/-- |  |  |  |  |  | 2/-- |  | 4/0
Star Dust | 2/-- |  |  |  |  | 1/60 | 3/-- |  | 6/1
brot kann schimmeln, was koennen wir?? | 1/-- |  |  |  |  | 1/143 |  |  | 2/1
Students of Steel | 3/-- |  |  |  |  |  |  | 2/252 | 5/1
Intelligence Inside | 2/-- |  |  | 3/-- |  | 1/133 |  | 7/284 | 13/2
Pinky | 1/-- |  |  | 3/-- |  | 1/126 | 5/283 |  | 10/2
Brain | 2/-- |  | 2/-- |  |  | 1/109 | 2/-- | 1/-- | 8/1
Team 9 | 1/-- |  |  | 1/-- | 3/196 | 1/125 | 3/-- | 3/208 | 12/3
Cyclic Crew | 4/-- |  |  | 4/-- |  | 1/126 | 5/-- |  | 14/1
freenode |  |  |  |  |  | 1/126 |  |  | 1/1
Ueberflieger | 2/-- |  |  | 2/196 |  | 1/75 | 7/-- |  | 12/2
Prajki |  |  |  |  |  |  |  |  | 0/0
Sphinx\\\\\\\'s Return | 4/-- |  |  | 2/-- | 1/-- | 1/128 |  |  | 8/1
Andromeda | 1/-- |  | 1/129 | 3/-- |  | 1/45 | 5/-- |  | 11/2
Die Einzelgaenger | 4/-- |  |  | 2/-- |  | 1/127 |  |  | 7/1
Soul Reaper | 6/-- |  |  | 2/-- |  | 1/44 |  | 4/-- | 13/1

Print Version