European Division South-western European Regional Contest
Selecção da Equipa da FEUP
2ª Prova
CICA, 1998 Abril 22
Problem 1
Background
Figure below gives an example of a course for a street race. You see some points, labeled from 0 to N (here N= 9), and some arrows connecting them. Point 0 is the start of the race; point N is the finish. The arrows represent one-way streets. The participants of the race move from point to point via the streets, in the direction of the arrows only. At each point, a participant may choose any outgoing arrow.
A well-formed course has the following properties:
-
Every point in the course can be reached from the start.
-
The finish can be reached from each point in the course.
-
The finish has no outgoing arrows.
A participant does not have to visit every point of the course to reach the finish. Some points, however, are unavoidable. In the example, these are points 0, 3, 6 and 9.
Problem
Given a well-formed course, write a program to determine the set of unavoidable points that all participants have to visit, excluding start and finish (Subtask A).
Suppose the race has to be held on two consecutive days. For that purpose the course has to be split into two courses, one for each day. On the first day, the start is at point 0, and the finish at some ‘splitting point’. On the second day, the start is at this splitting point and the finish is at point N. Given a well-formed course, your program has to determine the set of splitting points (Subtask B).
A point S is a splitting point for the well-formed course C if S differs from the start and the finish of C, and the course can be split into two well-formed courses that have no common arrows and that have S as only common point. In the example, only point 3 is a splitting point.
Input
The description of a well-formed course with at most 50 points and at most 100 arrows. There are N + 1 lines in the input. The first N lines contain the endpoints of the arrows that leave from the points 0 through N – 1 respectively. Each of these lines ends with the number –2. The last line contains the number –1.
Output
Two lines. The first line should contain the number of unavoidable points in the input course, followed by the labels of these points, in any order (Subtask A). The second line should contain the number of splitting points of the input course, followed by the labels of all these points, in any order (Subtask B).
Problem 1 example for the figure above
INPUT
1 2 –2
3 –2
3 –2
5 4 –2
6 4 –2
6 –2
7 8 –2
9 –2
5 9 –2
-1
OUTPUT
2 3 6
1 3
Problem 2
Background
Elves are clever creatures. Using their magic powers they may create smaller elves that create even smaller ones. The smallest elves must do all the work.
A clever elf must clean a very dirty forest house. Using his magic powers he took from his woolly hat smaller elves to do the job. These smaller intelligent elves cause even smaller elves to appear to do the work. This magic goes on and on until elves reach a smallest size. These unfortunate elves don't have magic powers and can not cause others to appear. They must do all the work. The number of elves that each elf (non-smallest) may cause to appear from his woolly hat is an integer constant N. The height of these magically born elves is 1/(1+N) times the height of their father elf. The smallest elves, that do all the work, are of height one, and all heights are positive integers.
Problem
Given the height of the initial elf and the number of the smallest elves, write a program to find the number of elves that are doing nothing and the sum of all elves heights.
Input
Several lines with two positive integers separated by a space. The first integer is the height of the initial elf and the second integer is the number of the smallest elves that do all the work. A pair of 0's on a line indicates the end of input.
Output
There should be one output line for each input line other than the line with "0 0". Each output line has to numbers separated by one space. The first is the sum of the heights of all elves. The second is the number of elves that are not working.
Problem 2 example
INPUT
64 27
59049 1024
0 0
OUTPUT
85 13
88573 1023
Problem 3
Background
A factory makes a modular fence system. The fence sections are one unit long and may be linked together using a separate joint. A joint always links two sections. Unfortunately, the machine that makes straight joints has broken down. The machine for right-angled (90º) joints still works, and can make left-handed and right-handed joints.
The factory’s computer scientist is asked to work out what shapes can be made with right-angled joints only. The computer scientist decides to describe a fence by a string of letters. Each letter tells whether the next section is joint to the left (L) or the right (R).
The string LRL describes a zigzag, consisting of 4 sections (Figure a; the joint ‘cut-off is greatly exaggerated). The string LLLL describes a closed square (Figure b). Some strings describe impossible shapes that intersect themselves, e.g. RLLLL.
From now on we consider only strings describing possible shapes that are closed.
A closed shape can be encoded in several ways, depending on where you start and the direction you go. For example, the strings LLLRLLLR and RLRRRLRR describe the same closed shape (Figure c).
Problem
Write a program that inputs a string describing a closed shape, and answers the following questions for this shape:
-
How large is the enclosed area, in square units? Space that can be reached from outside by squeezing in between two joints is not considered enclosed (see Figure d: the enclosed area is shaded).
-
Check whether a second string describes or not the same shape.
Input
Two lines. The first contains a single string, describing the shape. The second line contains the string to check. A string consists of at least 4 and at most 50 letters.
Output
Two lines. On the first line there is a single positive integer: the area enclosed by the shape. The second line is an answer YES or NO.
Problem 3 example (Figure c)
INPUT
LLLRLLLR
RLLLRLLL
OUTPUT
2
YES
Problem 4
Background
A word consists of at least one and at most 75 lowercase letters (from ‘a’ to ‘z’). A list of one or more words is called a chain when each word in that list, except the first, is obtained from the preceding word by appending one or more letters on the right. For instance, the list
i
in
int
integer
is a chain of four words, but the list
input
integer
is not a chain.
Problem
You are entitled to write a program that given a list of words calculates the longest chain of words taken from the input
The length of a chain is the number of words it contains.
Input
A list of words. The list contains at least one word and all of the words together have no more than 2,000,000 letters. The input is terminated with a line containing a single period ‘.’. All other lines contain one word each. The list is sorted lexicographically using the standard alphabetical ordering (as in an English dictionary). There are no duplicate words in the list.
Output
The longest chain of words taken from the input. Each word should be on a separate line. If there is more than one chain of maximum length, the program should output only one of these chains. It does not matter which one.
Problem 4 example
INPUT
i
if
in
input
int
integer
output
.
OUTPUT
i
in
int
integer
Problem 5
Background
Sorting is one of the most frequently done computational tasks. Consider the special sorting problem, where the records to be sorted have at most three different key values. This happens, for instance, when we sort medallists of a competition according to medal value, that is, gold medallists come first, followed by silver, and bronze medallists come last.
In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. Sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.
Problem
You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted (Subtask A). Moreover, construct a sequence of exchange operations for the respective sorting (Subtask B).
Input
The first line contains the number of records N (1 N 1000). Each of the following N lines contains a key value.
Output
The first line contains the minimal number L of exchange operations needed to make the sequence sorted (Subtask A). The following L lines give the respective sequence of the exchange operations in the order performed. Each line contains one exchange operation described by two numbers p and q, the positions of the two elements to be exchanged (Subtask B). Positions are denoted by the numbers from 1 to N.
Problem 5 example
INPUT
9
2
2
1
3
3
3
2
3
1
OUTPUT
4
1 3
4 7
9 2
5 9
Share with your friends: | 
997-1998 ACM International