Solutions pentru Etapa 9

Problem 1: Comunicatii
Problem 2: Baze
Problem 3: Radicali


Problem 1: Comunicatii

 
     Ideea algoritmului:

* se determina componentele conexe de cabane si se reduce fiecare componenta
  la o singura cabana - reprezentant - care "vede" tot ce "vad" cabanele
  componentei;
* se determina varfurile ce candideaza la alegerea in solutia optima in
  doi pasi:
            - se alege varful care vede un numar maxim de reprezentanti;
            - se formeaza un singur element din varful ales si reprezentantii
              vazuti;
* se "elimina" din vectorul de varfuri cele care sunt in plus astfel:
            - incepind de la primul varf ales se verifica daca multimea
              reprezentatilor vazuti de el este inclusa in reuniunea
              multimilor corespunzatoare celorlalte varfuri din vector;
            - in cazul in care este inclusa se verifica daca prin eliminarea
              acestui varf nu se pierde conexitatea ansamblului
              cabane+varfuri alese;
            - daca nu se pierde conexitatea se elimina varful din vector.

Majoritatea concurentilor n-au tinut seama de faptul ca pot aparea varfuri in
vector fara sa fie nevoie de ele. D-nul Mihai Stroe, care a obtinut cel mai
mare punctaj, a sesizat acest lucru, dar n-a facut "eliminarea" varfurilor
care erau in plus.


Punctajul acordat a fost:

 testul_1   -  1 punct
 testul_2   -  1 punct
 testul_3   -  2 puncte
 testul_4   -  2 puncte
 testul_5   -  2 puncte
 testul_6   -  2 puncte
 testul_7   -  2 puncte
 testul_8   -  3 puncte
 testul_9   -  3 puncte
 testul_10  -  3 puncte
 testul_11  -  5 puncte
 testul_12  -  4 puncte
     Total  - 30 puncte

Solution (Pascal)


Input files: 1 2 3 4 5 6 7 8 9 10 11 12 Output files: 1 2 3 4 5 6 7 8 9 10 11 12

Mult succes la viitoarele editii.



                        Prof.Cleopatra  Pau
                           "C.D.Loga" - Highschool
                                Timisoara

Problem 2: Baze

 

Problema a fost accesibila si a fost rezolvata de foarte multi
dintre participanti. Acest fapt ne bucura.


Verificarea s-a facut in doua situatii, create din vina noastra.
O prima situatie a fost aceea in care s-a citit din fisierul BYTE.IN o singura
linie, cu rezultate intr-un fisier BYTE.OUT.
A doua situatie a fost aceea in care s-au citit mai multe linii in fisierul
BYTE.IN, cu rezultate corespunzatoare in fisierul BYTE.OUT.



Programe bine realizate in 
Pascal
Fiind un comentariu mai scurt ne putem permite sa dam doua exemple de
programe C (program1 program2)foarte bine realizate, ale domnisoarelor Vastiana Mot si Katya Lilitko.

  Input files: 1 Output files: 1 
                                Prof.Maria si Adrian Nita
                                                                      Liceul "Emanuil Gojdu" - Oradea

Problem 3: Radicali

 

 


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

Go Back!