# Acm international Collegiate Programming Contest European Division

 Date 09.01.2017 Size 26.26 Kb. #8566

2ª Prova

## 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:

1. Every point in the course can be reached from the start.

2. The finish can be reached from each point in the course.

3. 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).

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:

1. 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).

2. 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.

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.

INPUT

9

2

2

1

3

3

3

2

3

1
OUTPUT

4

1 3

4 7

9 2

5 9