Distributed Programming Contest 2008

Contest Session
Universidad de Carabobo, Venezuela

November 08, 2008

This problem set should contain a rules section and nine (09) problems on thirteen (13) numbered pages.
Please inform the Contest Staff immediately if something is missing from your problem set.
Welcome to the Programming Contest and enjoy it!
Rules
• Each team will be provided with a single computer. All teams will have equivalent computing equip-
ment.
• There are nine (09) problems for each team to be completed in five (05) hours.
• All problems require that you read test data from the standard input and write results to the standard
output.

• You may use any of the following programming languages: C, C++ or Java. You may use different
programming languages for different problems and even for different submissions of a problem.
• All problems have a source file name shown below the title of the problem. The extensions you must
use for your source files are: .c for programs written in C, .cpp for those in C++, and .java for those
in Java.

• You may use any of the standard libraries that your chosen programming language provides. You may
not use any other library that requires an extra flag to be passed to the compiler command. If you do
this, judges will probably get a compilation-linking error in your program.
• Output corresponds exactly to the provided sample output format, including (mis)spelling and spacing.
Multiple spaces will not be used in any of the judges’ output, except where explicitly stated.
• Your solution to any problem should be submitted for judging using DOMjudge system (if you are
working in online mode) or PC2 software (if you are working in local mode). Once you have submitted
a solution, it will reach the judges. The time it takes for your problem to be judged will depend on
how busy the judges are. Once your submission has been judged, you will receive a message through
the DOMjudge or PC2 software indicating the judgment. If your solution is accepted the message will
be “Yes” or “Correct”, if it is not then the message will be “No” or “Incorrect”, along with the type of
error the judges encountered.
• Programming style is not considered in this contest. The judges will only test whether the input /
output behavior of your program is correct or not. However, each problem has an unknown execution
time-limit (in seconds). That is, if your program takes more than this time-limit to execute for the
given input, it will be judged as incorrect.
• Contestants may bring any printed materials (books, papers, documentation, source code of programs,
etc.) to the contest area, but no soft copy will be allowed (diskettes, CDs, DVDs, pen-drives, etc.).

1
 1 Recognizing h-sequences
Source file name: hseqs.c, [Link] or [Link]
An h-sequence is either a single 0 or it is a 1 followed by two h-sequences. Syntactically, h-sequences may be
defined by the following grammar expressed in BNF (Backus-Naur Form) notation:

hhi ::= 0 | 1 hhi hhi

Examples of h-sequences are:
0
100
10100
110010100
110100100
The programming problem is to determine for a given sequence x of n elements (n ≥ 0), whether x is an
h-sequence or not. For the sake of convenience, we assume that sequence x contains zeroes and ones only.

1.1 Input Format

The input begins with a single positive integer on a line by itself indicating the number of test cases, followed
by a blank line. Each case will consist of a sequence of ASCII 1’s and 0’s, one per line, terminated by a blank
line or the end-of-file marker. No line will have more than 80 characters.
The input must be read from standard input.

1.2 Output Format

For each input case, print a line indicating whether it is an h-sequence or not, according to the format in the
sample output.
The output must be written to standard output.

1.3 Sample Input

1 6
2 0
3 100
4 10100
5 110010100
6 110100100
7 1111111111

1.4 Output for the Sample Input

1 0 is an h-sequence.
2 100 is an h-sequence.
3 10100 is an h-sequence.
4 110010100 is an h-sequence.
5 110100100 is an h-sequence.
6 1111111111 is not an h-sequence.

2
2 S-Trees
Source file name: strees.c, [Link] or [Link]
A Strange Tree (S-tree) over the variable set Xn = {x1 , . . . , xn } is a complete binary tree representing a
Boolean function f : {0, 1}n → {0, 1}. Each of the S-tree’s nodes has a depth, defined as the number of nodes
in the path from the root to itself minus 1 (so the root has depth 0). The depth of any node in an S-tree is at
most n. The nodes with depth less than n are called non-terminal nodes, each having two children: the right
child and the left child. Each non-terminal node is labeled with some variable xi from the variable set Xn .
All non-terminal nodes with the same depth are labeled with the same variable, and non-terminal nodes with
different depth are labeled with different variables. So, there is a unique variable xi0 corresponding to the
root, a unique variable xi1 corresponding to the nodes with depth 1, and so on. The sequence of the variables
xi0 , xi1 , . . . , xin−1 is called the variable ordering. The nodes having depth n are called terminal nodes. They
have no children and are labeled with either 0 or 1. Note that the variable ordering and the distribution of
0’s and 1’s on terminal nodes are sufficient to completely describe an S-tree.
As stated earlier, each S-tree represents a Boolean function f . If you have an S-tree and values for the
variables x1 , . . . , xn , then it is quite simple to evaluate f (x1 , . . . , xn ): Start at the root and repeat the
following steps: if the node you are at is labeled with a variable xi , then depending on whether the value of
xi is 1 or 0, you go to its right or left child, respectively. Once you reach a terminal node, its label gives the
value of the function.

Figure 1: S-trees for the function x1 and (x2 or x3 )

In the picture, the two S-trees represent the same Boolean function:

f (x1 , x2 , x3 ) = x1 and (x2 or x3 )

For the left tree, the variable ordering is x1 , x2 , x3 , and for the right tree it is x3 , x1 , x2 . The values of the
variables x1 , . . . , xn , are given as a Variable Value Assignment (VVA) (x1 = b1 , x2 = b2 , . . . , xn = bn ) with
b1 , b2 , . . . , bn ∈ {0, 1}. For instance, (x1 = 1, x2 = 1, x3 = 0) would be a VVA for n = 3, resulting, for the
sample function above, in the value f (1, 1, 0) = 1 and (1 or 0) = 1.
Your task is to write a program which takes an S-tree and some VVAs and computes f (x1 , . . . , xn ) as described
above.

2.1 Input Format

The input contains the description of several S-trees with associated VVAs which you have to process. Each
description begins with a line containing a single integer n, 1 ≤ n ≤ 7, the depth of the S-tree. This is
followed by a line describing the variable ordering of the S-tree. The format of that line is xi1 xi2 . . . xin .
(There will be exactly n different single space-separated strings). So, for n = 3 and the variable ordering
x3 , x1 , x2 , this line would look as follows

x3 x1 x2

In the next line the distribution of 0’s and 1’s over the terminal nodes is given. There will be exactly 2n
characters (each of which can be 0 or 1), followed by the new-line character. The characters are given in the

3
 order in which they appear in the S-tree, the first character corresponds to the leftmost terminal node of the
S-tree, the last one to its rightmost terminal node.
The next line contains a single integer m, the number of VVAs, followed by m lines describing them. Each
of the m lines contains exactly n characters (each of which can be 0 or 1), followed by a new-line character.
Regardless of the variable ordering of the S-tree, the first character always describes the value of x1 , the
second character describes the value of x2 , and so on. So, the line

110

corresponds to the VVA (x1 = 1, x2 = 1, x3 = 0).

The input is terminated by a test case starting with n = 0. This test case should not be processed.
The input must be read from standard input.

2.2 Output Format

For each S-tree, output the line “S-Tree #j”, where j is the number of the S-tree. Then print a line that
contains the value of f (x1 , x2 , . . . , xn ) for each of the given m VVAs, where f is the function defined by the
S-tree. Output a blank line after each test case.
The output must be written to standard output.

2.3 Sample Input

1 3
2 x1 x2 x3
3 00000111
4 4
5 000
6 010
7 111
8 110
9 3
10 x3 x1 x2
11 00010011
12 4
13 000
14 010
15 111
16 110
17 0

2.4 Output for the Sample Input

1 S-Tree #1
2 0011
3

4 S-Tree #2
5 0011
6

4
 3 See You in XCNGPEKC at 60◦
Source file name: seeyou.c, [Link] or [Link]
A well known network of drug dealers has designed a special encryption method to encode the hour and
place where they will receive their packages. This method uses the position of an analog clock hour hand
(measured in degrees) to represent an hour, a positive integer which represents the number of characters of
the alphabet to count backwards to find each correct character of the word, and an encrypted word. The
Intelligence Department of the police has found a complete list of the next arrival times and places of the
packages, and your job is to write a program capable of decoding the information.

3.1 Input Format

The input consists of a series of lines. Each line of the input should contain two numbers and a word. The
first number is a real value d (0 ≤ d ≤ 360) that represents the degrees of the analog clock hour hand, which
is the exact arrival hour of the packages. The second number is a positive integer m (1 ≤ m ≤ 25) that
represents the movement used to encrypt the characters of the arrival place, and the word p represents the
arrival place. For example, if the tuple is 60.00 2 XCNGPEKC, the arrival hour is 01:00:00, the movement is
2, and the encrypted word is XCNGPEKC, so the characters of the original word will be the ones 2 positions
before the ones in the encrypted word, resulting in the word VALENCIA.
The input must be read from standard input.

3.2 Output Format

For each line in the input, your program should write the decoded hour (in the format hh:mm:ss) and the
decoded word, separated between them by exactly one blank space.
The output must be written to standard output.

3.3 Sample Input

1 235.750000 2 XCNGPEKC
2 0.000000 4 GEVEFSFS
3 360.000000 25 EZKBNM
4 60.125000 11 AZCEFRFPDL

3.4 Output for the Sample Input

1 07:08:30 VALENCIA
2 03:00:00 CARABOBO
3 03:00:00 FALCON
4 12:59:45 PORTUGUESA

5
 4 Led Codes
Source file name: ledcode.c, [Link] or [Link]
Some led systems display characters as a combination of lightlines, much like digital calculators do. Suppose
we have one of such led systems, in which each letter of the standard English alphabet is constructed
combining some of ten possible lightlines, numbered as below:

For instance, the letter A is shown using the lines 1, 2, 3, 4, 5 and 7. With these few lines it is not possible,
of course, to show all the 26 letters with their natural shapes. A complete list of the letters of our system is
appended at the end.
You have to solve the problem of decoding a combination of numbers (representing lightlines) in the form of
the respective letter, to form a whole word or phrase. As input you have a string of letters and/or numbers,
and as output you must show only the letters.

4.1 Input Format

The input begins with a line containing a single integer N , that indicates the number of input examples,
followed by N lines, each one representing an input phrase. Each input phrase consists of lowercase letters,
blank spaces and/or digits. In the case of digits, their combination must form valid led letters. Each letter
is coded as a combination of numbers, ordered in the form 1, 2, 3, 4, 5, 6, 7, 8, 9, 0. A zero (0) that is not part
of a valid letter code, is interpreted as a blank space.
You may assume that no invalid codes are entered, and that the system does not allow ambiguity between
two letter codes.
The input must be read from standard input.

4.2 Output Format

The output consists of N lines (one for each input string) with the form:

Phrase 1: .....
Phrase 2: .....

where the dots are, of course, the result of the decoding process. The alphabetic letters and blank spaces
must not be decoded at all: only the numbers must be converted to the corresponding led letters.
The output must be written to standard output.

4.3 Sample Input

1 3
2 HELL1235670WO1234591561580
3 PROGRAMMING037124670C123567123567156
4 AND MORE037124903735790278134573712467045612356735792781245612467278

6
 4.4 Output for the Sample Input
1 Phrase 1: HELLO WORLD
2 Phrase 2: PROGRAMMING IS COOL
3 Phrase 3: AND MORE IF IN THIS CONTEST

4.5 Complete List of Letters

7
 5 Counting Graphs
Source file name: counting.c, [Link] or [Link]
A simple graph is an unweighted, undirected graph containing no loops (a loop is an edge that connects a
vertex to itself) or multiple edges. In this problem you have to count the number of simple graphs without
isolated nodes that you can build using n nodes.

5.1 Input Format

The input consists of a series of lines. Each line of the input should contain an integer n (1 ≤ n ≤ 30) that
indicates the number of graph nodes. The input will be terminated by end of file.
The input must be read from standard input.

5.2 Output Format

For each test case in the input, you must write the number of simple graphs without isolated nodes that you
can build, according to the format specified in the example below.
The output must be written to standard output.

5.3 Sample Input

1 1
2 2
3 3
4 4
5 5
6

5.4 Output for the Sample Input

1 Case #1: 0
2 Case #2: 1
3 Case #3: 4
4 Case #4: 41
5 Case #5: 768
6

8
 6 Cable Network
Source file name: cn.c, [Link] or [Link]
A local cable network is planning to expand their services to a neighboring city. For that, a transmission
center is being built and a cable net connecting the new clients has to be installed. Each client has to be
connected to the center in the cable net.
The network organized a survey and has now the addresses of all potential clients. Also it has an estimate
on the cost of installing each cable link through the city.
The network board of directors has decided to offer the following initial subscription package: Each new client
will pay a fixed subscription fee and will get the first three months of service for free. This ensures a potential
initial capital for building the cable net, which is simply the number of potential clients (according to the
survey) multiplied by the subscription fee.
The decision on what links to build in this first phase will be done according to the following. A set of links
induces a loss in the potential initial capital, defined as l + (t × d), where l is the cost of installing the
links in the set, t is the subscription fee and d is the number of potential clients that are not connected to
the center by this set of links. The board of directors decided they will build a set of links that induces a
loss as small as possible in the potential initial capital.
Your job is to write a program to compute the minimum possible loss in the potential initial capital. For
that, you are given the location of each potential client as well as the center location. Also, you are given
the costs of all possible net links and the value of the subscription fee.

6.1 Input Format

The input contains the description of several instances. An instance with n = 0 indicates the end of the
input. Your program should not process this instance.
The first line contains two positive integers: n (0 ≤ n ≤ 20) representing the number of potential clients and
t representing the subscription fee. Each potential client is identified by a number between 1 and n while
the center is identified by 0. Next, there is a line for each i from 0 to n − 1. In line i there is a list of n − i
positive integers. Each integer, say the j-th one, represents the cost of installing a link between i and j.
The input must be read from standard input.

6.2 Output Format

For each instance, your program should print three lines; the first contains “Cable Net #j”, where j is the
number of the instance; in the second line, it should print the potential initial capital for that instance and in
the third line, the value of the minimum possible loss in the potential initial capital for that instance. Your
program should also print a blank line after the output of each instance.
The output must be written to standard output.

6.3 Sample Input 6.4 Output for the Sample Input

1 5 10 1 Cable Net #1
2 5 17 2 3 23 2 50
3 9 6 1 19 3 21
4 14 5 13 4

5 19 21 5 Cable Net #2
6 40 6 3
7 3 1 7 3
8 5 3 23 8

9 1 19
10 14
11 0 1

9
7 Magic Squares
Source file name: magic.c, [Link] or [Link]
Among the oldest and most popular forms of mathematical recreations are magic squares. A magic square
of order n is an n × n array constructed out of the integers 1, 2, 3, . . . , n2 in such a way that the sum s of the
integers in each row, in each column, and in each of the two diagonals is the same. The number s is called
the magic sum of the magic square. Examples of magic squares of order 3 and 4 are
 
8 1 6
3 5 7 (1)
4 9 2
 
16 3 2 13
 5 10 11 8 

9
 (2)
6 7 12
4 15 14 1
with magic sum 15 and 34 respectively. In medieval days there was a certain mysticism associated wirh magic
squares, and they were worn for protection against evils. Benjamin Franklin was a magic square fan, and his
papers contain many interesting examples.
We describe here a method found by de la Loubère in the seventeenth century for constructing magic squares
of order n when n is odd. First a 1 is placed in the middle square of the top row. The successive integers
are then placed in their natural order along a diagonal line which slopes upwards and to the right, with the
following modifications:

1. When the top row is reached, the next integer is put in the bottom row as if it came immediately above
the top row.
2. When the right-hand column is reached, the next integer is put in the left-hand column as if it imme-
diately succeeded the right-hand column.
3. When a square is reached which has already been filled or when the top right-hand square is reached,
the next integer is placed in the square immediately below the last square which was filled.

The magic square of order 3 in (1) was constructed using the de la Loubère’s method, as was this magic
square of order 5:
 
17 24 1 8 15
23 5 7 14 16
 
4 6 13 20 22 (3)
 
10 12 19 21 3 
11 18 25 2 9

Your task is to write a program that constructs a magic square of odd order up to 255 using the de la
Loubère’s method described above.

7.1 Input Format

The input will contain one or more test cases. Each test case consists of one line containing one integer,
representing the order of the magic square. The end of input stream is marked by the number zero.
The input must be read from standard input.

10
 7.2 Output Format
The output will consist of one magic square for each positive integer in the input. Each magic square must
be separated by a blank line. The output must be formatted as shown in the example below:
• The numbers are outputted in columns of the same width.

• The numbers are right justified within columns.

• Each column of numbers must be separated by only one column of blank spaces.
The output must be written to standard output.

7.3 Sample Input

1 3
2 5
3 7
4 0

7.4 Output for the Sample Input

1 8 1 6
2 3 5 7
3 4 9 2
4

5 17 24 1 8 15
6 23 5 7 14 16
7 4 6 13 20 22
8 10 12 19 21 3
9 11 18 25 2 9
10

11 30 39 48 1 10 19 28
12 38 47 7 9 18 27 29
13 46 6 8 17 26 35 37
14 5 14 16 25 34 36 45
15 13 15 24 33 42 44 4
16 21 23 32 41 43 3 12
17 22 31 40 49 2 11 20
18

11
 8 Move the Water
Source file name: water.c, [Link] or [Link]
You have three jars containing water. Each jar has associated a capacity indicating the maximum amount
of water it can contain. Your wish is to have a certain amount of water in each jar. The initial content of
each jar, its capacity, and the desired content, are all non negative integers; in addition, the capacities are
between 1 and 150. You have nothing but the jars to help you in achieving your goal. So the only way to
obtain the desired content in each jar is to make a sequence of movements of water. In a movement of water
you pour a certain amount of water from one jar to another jar. We call the first jar source and the second
jar destination. While moving water two situations can occur: If the current content of the source jar is not
enough to complete the capacity of the destination jar, then all the water contained in the source jar is moved
to the destination jar; otherwise, only the exact amount of water needed to complete the destination jar is
moved from the source jar. Under no circumstances you can use additional water or throw away water. Your
task is to determine the minimum number of movements required to obtain the desired amount of water in
each jar.

8.1 Input Format

The input contains a certain number of test cases for this problem. Each test case is given in a single line
containing nine values c1 , c2 , c3 , a1 , a2 , a3 , b1 , b2 , b3 ; these values are separated by an arbitrary number of
blank spaces. The value ci is the capacity of the i-th jar, ai is its initial content, and bi is the desired content
for the jar. In the last line of the input c1 has value equal to 0; this line should not be processed.
The input must be read from standard input.

8.2 Output Format

For each test case in the input, the output must contain a line with the minimum number of movements
required to obtain the desired content in each jar. If for a given test case there is no solution, you must write
the value −1 instead of the number of movements.
The output must be written to standard output.

8.3 Sample Input

1 5 4 1 1 0 1 0 2 0
2 5 4 1 1 0 1 0 3 0
3 5 4 1 1 0 1 0 0 2
4 5 4 1 1 0 1 1 0 1
5 5 4 1 0 4 0 3 0 1
6 0 1 1 0 0 0 0 0 0

8.4 Output for the Sample Input

1 2
2 -1
3 -1
4 0
5 2

12
 9 The Red Baron
Source file name: redbaron.c, [Link] or [Link]
Well, this time, is a little hard for you. . . One of your friends nickname is ‘speedracer’, known also as ‘Red
Baron’, because he seems to be flying in his white car. Your fast and furious friend knows that you are an
excellent programmer, and he needs that you do some software for him.
Lately the competence has turned into the streets, it means that you have tons of semaphores and the rules
say that you must respect them.
He measured up all the semaphores lights in the different tracks on the city, and he was wondering if it is
possible that you design a program that let him know at which constant speed he should drive to pass free
through all the semaphores without being stopped.
At a specific time in the night, the staff knows that all the semaphores in the track get synchronized, and
begin in red light at the same time, so that’s the moment when the race begins.
You must consider that he can pass free with yellow and green lights; his plane, oops, his car, takes 11
seconds and 700 meters to reach 300 Km/h (maximum speed of the car without being broken), also you must
consider that at the moment he accelerates by the first time the semaphore is beginning red. In case he got
to stop, he prefers not to run that track. Could you be able to calculate the maximum constant speed he
should drive?

9.1 Input Format

The input consists of a series of lines. The first line has an integer n (0 < n < 10000) that indicates the
number of semaphores that you must consider for the problem. Then you must read n lines, where the
first number indicates, the kilometer where the semaphore locates, the second integer indicates the red light
timing, the third indicates the yellow light timing, and the last integer of the line indicates the green light
timing in seconds all of them.
The input must be read from standard input.

9.2 Output Format

You must print the speed “The maximum speed is N.”, where N is the speed at that case. In case your friend
has to stop at any time, you must print “This track is not good for you”, and the time he passed the
last semaphore.
The output must be written to standard output.

9.3 Sample Input

1 5
2 1 2 3 5
3 2 1 4 2
4 8 3 5 2
5 12 1 3 5
6 15 0 4 6
7 2
8 1.5 40 1 1
9 2 5 5 5

9.4 Output for the Sample Input

1 The maximum speed is 300.
2 The maximum speed is 123.
3

13