Solutions for Round 8

Problem 1: Policemen at Work
Problem 2: Languages
Problem 3: Polygons

Problem 1: Policemen at Work


The problem doesn't request an algorithm of exponential complexity.The graph on which the problem is shaped is not connex, but let's think the algorithm over for a connex compound of the graph.We consider N1 points and M1 edges in this connex compound.
- if the tree is made in the BF running (as it will have fewer levels),M1-N1-1 edges will remain unselected in the tree.
All these close a cicle inside the tree.These will be the routesgiven to the policemen.We will take, in turns, an edge (i1,j1) that is not put in the tree and we will re-make the way (possibly minimum in length), from the knot i1 to the knot j1.In this way, working on each connex compound, we shall obtain all the routes, plus the number of cicles, independently maximal (any two have a distinct edge), also called a ciclomatic number, which will be M - N - + K, where K is the number of connex compounds.

The tests shall be sent as attached documents.

The given score was, corresponding to the (9) tests:

3 3 3 3 4 4 4 3 3 = 30 points.

Well - done solutions in
Pascal and C

Input files: 1 2 3 4 5 6 7 8 9  Output files: 1 2 3 4 5 6 7 8 9 
                                 Daniela  Lica
                         "Ion Luca Caragiale" - Highschool

Problem 2: Languages

We gave the problem as an example of formal language.
By 'formal language' we understand a multitude of finite strings made up of elements in an alphabet of primitive symbols.

These strings are called words or sentences, correct from a gramatical point of view.To select words, we consider a finite set of rules called Gramathics. The defining of a formal language is transfered into the problem of defining both the gramatic that generates this language and the way in which the gramatic's rules selects the language's words.

Many of the solutions use oriented graphs and very elegant solutions.

A large number of sources got a maximum score.

Solution no. 1 (Pascal) Solution no. 2 (C)

Input files:
Words: 1 2 3 4 5 6 7 8
Dictionaries: 1 2 3 4 5 6 7 8

Output files: 1 2 3 4 5 6 7 8


Maria and Adrian Nita,
Aniko Sos
"Emanuil Gojdu" High School - Oradea

Problem 3: Polygons

The "algorithm" could be described in a single line:
- for n sides (n >= 4), the number of diagonals is:
(n * (n - 1) * (n - 2) * (n - 3)) Div 24

The only difficulty lies in the making of the product in which big
numbers occur.(n <= 100 000 000)

The input file will be: DIAG.IN, and the output file will be: DIAG.OUT

Solution no. 1 (Pascal) Solution no. 2 (C) or Solution no. 3 (C)

Input files: 1 Output files: 1

We are sorry that there were sources which tried to calculate directly the
number of diagonals and, outrunning the domain, couldn't obtain a maximum
We wish you luck, even if for a short time now...

Maria and Adrian Nita teachers,
"Emanuil Gojdu" High School - Oradea

[The problems] [First Round] [Previous Round] [Next Round] [Current Round] [Romāna] [Go Back!]

Go Back!