Moto: "Sa judeci un om ca este capabil de lucruri mari,
       dupa atentia pe care o da celor mici."
                                 ( Tacit )




                   POLITISTI PE TEREN   - 30 puncte
                   ^^^^^^^^^^^^^^^^^^


      Intr-o metropola, noul sef al Serviciului Circulatie din Politie,
incearca sa micsoreze numarul de subordonati care stau fara sa aiba de lucru
in birouri. In acest scop doreste sa trimita pe teren cat mai multi politisti
pentru a supraveghea anumite strazi ale orasului.
 Pentru a-i controla mai usor fiecarui politist ii va fi repartizat un traseu.
 Prin traseu, seful intelege o secventa de strazi fiecare strada fiind
identificata prin cele doua intersectii care o delimiteaza.
 La stabilirea traseului pentru fiecare politist in parte, se tine cont de
urmatoarele cerinte:
   - din orice punct de intersectie al traseului, politistul poate sa
strabata toate strazile acestuia, o singura data, intorcandu-se intotdeauna
in punctul de plecare;
   - in final orice traseu repartizat unui politist trebuie sa aiba cel putin
o strada nesupravegheata de restul politistilor aflati in patrulare.

Determinati numarul maxim de politisti care pot fi trimisi pe teren,
precum si traseul repartizat fiecaruia( fiecare traseu fiind scris
in ordinea parcurgerii lui).


DATELE DE INTRARE:
^^^^^^^^^^^^^^^^^
Fisierul de intrare INPUT.TXT are urmatoarea structura:

n m          // pe prima linie numerele
                n (n <= 1500), reprezentand numarul de intersectii din oras,
                m (m <= 5000), reprezentand numarul srazilor;
i   i        // urmatoarele m linii contin perechi de doua numere,
 11  12         reprezentand  identificatorii intersectiilor la care este
                conectata fiecare strada.
i   i
 21  22
....

i   i
 m1  m2


DATELE DE IESIRE:
^^^^^^^^^^^^^^^^
Fisierul OUTPUT.TXT are urmatoarea structura:

p                     // pe prima linie se scrie numarul maxim de politisti
                         care pot fi trimisi pe teren;
t   t   ... t
 11  12      1k1

t   t   ... t         // pe urmatoarele p linii se vor scrie traseele
 21  22      2k2         atribuite politistilor, pentru fiecare traseu
                         precizandu-se intersectiile aflate pe acestea;
 ....                    datele de pe fiecare linie se vor desparti prin
t   t        t           cate-un spatiu
 p1  p2       pkp


Exemplu:
^^^^^^^
INPUT.TXT:                          OUTPUT.TXT:
7 10                                4
1 2                                 1 2 6 1
1 6                                 2 3 6 2
2 6                                 3 6 5 4 3
2 3                                 3 5 4 3
3 4
3 5
3 6
4 5
5 6
5 7

Timp maxim de executie: 30 sec/test pentru 586/133MHz.


                                 Prof. Daniela Lica
                             Liceul "Ion Luca Caragiale"
                                     Ploiesti






                   LIMBAJE ... - 30 puncte
                   ^^^^^^^


     Se construieste un limbaj nou, avand urmatoarele elemente:
     - un sistem format din n stari, n <= 200.
     - un alfabet, format din caractere litere mici din alfabetul englez;
     - o stare initiala;
     - o multime de stari finale;
     - o functie care descrie evolutia starilor in functie de caracterele
       introduse in alfabet;
     Un sir de caractere formeaza un cuvant, al limbajului descris mai sus,
                                     ^^^^^^
daca pornind de la starea initiala, urmarind functia de evolutie se ajunge la
o stare finala.

Cerinte:
^^^^^^^
Datele de intrare se citesc din:
 - fisierul DICTION.TXT avand urmatoarea structura:

n                        // numarul de stari;
c  c  c  ... c           // reprezentand caracterele alfabetului,
 1  2  3      r             despartite prin spatiu;

i                        // numarul de ordine al starii initiale;
                            1 <= i <= n;
k  k  k  ... k           // numarul de ordine al starilor finale,
 1  2  3      l             numere naturale despartite prin spatiu;
                            0 < l <= n;

s     ...    s
 1 1          1 i1       // pe urmatoarele n * n  linii se descrie
s     ...    s
 2 1          2 i2          functia de evolutie astfel:
                            - pe primele n linii pentru c1 evolutia
..                           prin cele n stari, s.a.m.d.
s       ...  s              - "0" desemneaza multimea vida.
 n^2 1        n^2 in^2


 - fisierul CUVINTE.TXT  contine pe m linii cuvinte:

cuvant_1
cuvant_2
...
cuvant_m

In fisierul CUVINTE.TXT se vor introduce cuvinte formate doar din
caracterele permise( cele introduse in DICTION.TXT)

Datele de iesire se scriu in fisierul LIMBAJ.TXT, care are structura:
 - pe m linii se scrie "YES" sau "NO", dupa cum cuvantul de pe linia
 corespunzatoare este sau nu cuvant al limbajului realizat.


Exemplu:
^^^^^^^
DICTION.TXT:                                CUVINTE.TXT:
4                                           abb
a b                                         aabaa
1                                           aaab
3 4                                         bbb
2 3 4                                       abaa
0
4
3
1 3
2 4
0
1

Fisierul de iesire este LIMBAJ.TXT:

YES
YES
NO
YES
YES

Timp maxim de executie 10 sec/test, pentru 586/133MHz.



                               Prof. Maria si Adrian Nita
                                 Prof. Aniko Sos
                              Liceul Teoretic "Emanuil Gojdu"
                                        Oradea





                        POLIGOANE... - 15 puncte
                        ^^^^^^^^^

  Se considera un poligon convex cu n laturi, n <= 100 000 000.
  In cate puncte se intersecteaza diagonalele sale stiind ca nu exista
nici un grup de trei diagonale care sa fie concurente?

Restrictii:
^^^^^^^^^^
Datele se citesc din fisierul DIAG.IN avand structura:

n1
n2          // ni reprezinta numarul de laturi ale poligonului
..
nk


Rezultatele se scriu in fisierul DIAG.OUT cu structura:

p1
p2          // pi reprezinta numarul de intersectii corespunzator
..         // poligonului cu ni laturi.
pk


Timp de executie 0.5 sec/test pentru 586/133 MHz.


                             Prof. Maria si Adrian Nita
                           Liceul Teoretic "Emanuil Gojdu"
                                      Oradea


--------------------------------------------------------------------------

Corectare pt. etapa 8, problema 2:

 - fisierul DICTION.TXT are urmatoarea structura:

n                        // numarul de stari;
c  c  c  ... c           // reprezentand caracterele alfabetului,
 1  2  3      r             despartite prin spatiu;

i                        // numarul de ordine al starii initiale;
                            1 <= i <= n;
k  k  k  ... k           // numarul de ordine al starilor finale,
 1  2  3      l             numere naturale despartite prin spatiu;
                            0 < l <= n;

s     ...    s
 1 1          1 i1       // pe urmatoarele n * r  linii se descrie
s     ...    s                                ^^^
 2 1          2 i2          functia de evolutie astfel:
                            - pe primele n linii pentru c1 evolutia
..                           prin cele n stari, s.a.m.d.
s       ...  s              - "0" desemneaza multimea vida.
 n*r 1        n*r in*r
