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:123456789Output files:123456789

Teacher Daniela Lica "Ion Luca Caragiale" - Highschool Ploiesti

**Problem 2:**Languages

We gave the problem as an example of formal language.

Definition:

^^^^^^^^^^

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

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

score.

We wish you luck, even if for a short time now...

MariaandAdrian Nitateachers,

"Emanuil Gojdu" High School - Oradea

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