Rezolvari pentru Etapa 8

Problema 1: Politisti pe teren
Problema 2: Limbaje
Problema 3: Poligoane


Problema 1: Politisti pe teren

Problema nu necesita un algoritm de complexitate exponentiala.

Graful pe care se modeleaza problema nu este conex, dar sa gandim
algoritmul pentru o componenta conexa a acestuia.
Consideram ca avem N1 puncte si M1 muchii in aceasta componenta conexa.
 - daca se creaza arborele in parcurgerea BF (intrucat va avea
mai putine nivele) vor ramane neselectate in arbore M1-N1-1 muchii.
   Toate acestea inchid in arbore cate un ciclu. Acestea vor fi traseele care
vor fi atribuite politistilor.
   Deci se va lua pe rand cate o muchie (i1,j1) nepusa in arbore si se va
reface drumul (eventual minim ca lungime), de la nodul i1 la
nodul j1.
   In felul acesta lucrand pe fiecare componenta conexa vom obtine toate
traseele si in plus numarul de cicluri independent maximale (oricare doua
au o muchie distincta), numit si numar ciclomatic, care va fi M - N + K,
unde: K este numarul de componente conexe.


Testele vor fi trimise ca document atasat.

Well - done solutions in
Pascal and C


Fisiere de intrare: 1 2 3 4 5 6 7 8 9
Fisiere de iesire: 1 2 3 4 5 6 7 8 9



                        Profesor
                                                           Daniela  Lica
                                                Liceul "Ion Luca Caragiale"
                                                               Ploiesti

 


Problema 2: Limbaje

Problema s-a dorit un exemplu de limbaj formal.
Definitie:

Prin limbaj formal se intelege o multime de siruri finite de elemente
dintr-un alfabet de simboluri primitive.

Aceste siruri sunt numite cuvinte sau propozitii corecte din punct de vedere
gramatical. Pentru a selecta cuvinte, se considera o multime finita de reguli
numita gramatica. Definirea unui limbaj formal se transpune in problema
definirii gramaticii care genereaza acest limbaj si a modului in care regulile
gramaticii selecteza cuvintele limbajului.

Multe din solutii folosesc grafurile orientate si dau solutii foarte elegante.

Un numar mare de surse au luat punctaj maxim.


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

Fisiere de intrare: 
Cuvinte: 1 2 3 4 5 6 7 8 
Dictionare: 1 2 3 4 5 6 7 8 

Fisiere de iesire: 1 2 3 4 5 6 7 8 


Maria si Adrian Nita, Aniko Sos
Liceul "Emanuil Gojdu" - Oradea


Problema 3: Poligoane

"Algoritmul" ar putea fi descris intr-un singur rand:
- pentru n laturi (n >= 4), numarul de diagonale este:
(n * (n - 1) * (n - 2) * (n - 3)) Div 24

Singura dificultate consta in realizarea produselor in care intervin
numere mari.(n <= 100 000 000)

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


Input files: 1 Output files: 1 

Ne pare rau ca au fost surse care au incercat un calcul direct al
numarului de diagonale dar, depasind domeniul nu au reusit sa obtina
punctaj maxim.
Va dorim succes, chiar daca pentru inca putin timp

Prof. Maria si Adrian Nita,
Liceul "Emanuil Gojdu" - Oradea


[Enunturile] [Etapa 1] [Etapa anterioara] [Etapa urmatoare] [Etapa curenta] [English] [Inapoi!]

Inapoi!