
                     ETAPA V - 3 probleme 
                     ^^^^^^^   3 problems

  Moto: " Un 'ciclu' oricat de perfect ar fi are o conditie de iesire."
                                     ( Folclor - Info.)



                  PROBLEMA 1
                  ^^^^^^^^^^

               LEGEA SI ORASELE   ( 30 puncte )


        Parlamentul doreste sa adopte o lege foarte importanta, dar pentru
asta trebuie sa primeasca date despre orasele tarii. Ca urmare i se cere
fiecarui primar informatii despre orasul condus de el.  Fisierele primite
de la primari nu sunt lesne de descifrat, de aceea trebuie rescrise pe
intelesul tuturor.
        Despre fiecare oras se stie ca este compus din mai multe cartiere de
locuinte. Cartierele sunt delimitate de sosele care le inconjoara, neexistand
sosele in interiorul niciunuia dintre ele.

        In fiecare oras exista cu siguranta doua tipuri de centuri:
        * Centura fiecarui cartier formata din soselele care il
delimiteaza (inconjoara).
        * Centura orasului formata din soselele ce inconjoara toate
cartierele. Evident aceasta centura este compusa din sosele ce la randul
lor fac parte si  din centurile unor cartiere limitrofe.

        Observatii:
        * Soselele sunt drepte.
        * Intr-o intersectie pot intra doua sau mai multe sosele.
        * Intre oricare doua intersectii exista cel putin doua drumuri
(succesiuni de sosele) care nu au nici o sosea in comun.

        Parlamentul doreste sa afle cate cartiere are fiecare oras si care
sunt centurile orasului si cartierelor acestuia.

Intrare: Fisierul de intrare se numeste INPUT.TXT si are urmatorul format:
^^^^^^^^
n m             - n este numarul de intersectii, iar m numarul de sosele
x1 y1           - coordonatele in plan a intersectiei 1
.......
xn yn           - coordonatele in plan a intersectiei n
q1 w1           - sosea intre intersectile q1 si w1
........
qm wm           - sosea intre intersectile qm si wm

Iesirea se va face in fisierul text OUTPUT.TXT sub urmatoarea forma:
^^^^^^^
* pe prima linie numarul C de cartiere ale orasului;
* pe urmatoarele C+1 linii vor fi scrie centurile cartierelor si a orasului,
specificate prin numarul de ordine a intersectiilor situate pe ele,
scrise in ordinea obtinuta la parcurgerea centurii.
Numerele de ordine ale intersectiilor vor fi despartite printr-un spatiu si
ultima intersectie din centura va fi si prima.

Limite: Toate numerele ce apar in problema sunt numere naturale mai mici
             decat 5001.
Timp per test: o secunda/Pentium 166 Mhz.

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

Exemplu 2:
^^^^^^^^^^
INPUT.TXT                       OUTPUT.TXT
4 4                             1
1 1                             1 2 4 3 1
2 1                             1 2 4 3 1
1 2
2 2
1 2
3 4
1 3
2 4


                                    Valentin Gheorghita
                               UPB, Facultatea de calculatoare



                    PROBLEMA II
                    ^^^^^^^^^^^

                    JOCUL NIM  ( 25 puncte )

Regulile jocului nim:
^^^^^^^^^^^^^^^^^^^^^
* Nim este un joc de strategie jucat de doi parteneri pe o masa cu n gramezi
  de betisoare.
* Cei doi parteneri parteneri sunt programul tau si biblioteca de evaluare.
* Programul tau face intotdeauna prima mutare.
* Partenerii fac alternativ cate o mutare. O mutare consta in extragerea
  unui numar arbitrar(>0) de betisoare dintr-o singura gramada.
* Un jucator pierde daca nu mai poate muta, adica toate gramezile de pe
  masa au exact zero betisoare.

Problema:
^^^^^^^^^
* Scrieti un program care joaca nim.
* Scopul primului jucator(programul tau) este de a lasa masa goala, adica de
  a castiga.
* Celalalt jucator (biblioteca de evaluare) incearca la randul ei sa castige.
* Daca programul tau joaca bine va castiga pe toate testele furnizate la
  evaluare.

Intrare si iesire:
^^^^^^^^^^^^^^^^^^
* Programul tau nu foloseste nici un fisier pentru citire si scriere; de
  asemenea nu va citi de la tastatura si nu va afisa nimic pe ecran.
  El va primi toate datele de intrare din biblioteca NimLib.

Restrictii:
^^^^^^^^^^^
* Toate numerele returnate de biblioteca NimLib vor fi intregi apartinand
  intervalului [1..10000].
* Un joc este terminat cand unul dintre jucatori castiga.
  Un joc trebuie terminat in 2 secunde (pe Pentium/166mhz).
  Se garanteaza ca biblioteca de evaluare isi termina partea sa de mutari
  intr-o secunda.

Biblioteca:
^^^^^^^^^^^
* O biblioteca numita NimLib este accesibila si trebuie folosita de
  programul tau:
   * in Pascal : Uses NimLib
   * In C : #include<NimLib.h>
* Functiile si procedurile din NimLib sunt (in ordine in Pascal si C):
   * function NumberOfHeaps : Integer;
     int NumberOfHeaps(void) ;
        Returneaza numarul de gramezi de pe masa.
   * function NumberInHeap(Heap : Integer) : Integer;
     int NumberInHeap( int Heap);
        Returneaza numarul de betisoare din gramada Heap.
   * procedure MyMove(Heap, Number : Integer);
     void MyMove( int Heap ; Int Number);
       Apelarea procedurii semnifica extragerea, de catre programul tau,
       a Number betisoare din gramada Heap.
       Daca procedura nu va opri programul tau ea va returna in variabilele
       ComputerMoveHeap si ComputerMoveNumber mutarea bibliotecii de evaluare
       ce succede mutarea ta.
       Aceasta procedura opreste programul tau daca:
         1. Programul tau a castigat jocul.
         2. Biblioteca de evaluare a castigat jocul.
         3. Mutarea programului tau este incorecta
* Variabilele din NimLib sunt(in ordine in Pascal si C):
   * ComputerMoveHeap : Integer;
     int ComputerMoveHeap;
        Gramada din care extrage biblioteca de evaluare la mutarea ei ce
        succede mutarea programului tau.
   * ComputerMoveNumber : Integer;
     int ComputerMoveNumber;
        Numarul de betisoare pe care le extrage biblioteca de evaluare la
        mutarea ei ce succede mutarea programului tau.

Scorul:
^^^^^^^
* Daca programul tau castiga un joc el va primi punctajul maxim pentru acel
  test.
* Daca programul tau pierde un joc el va primi 20% din punctajul testului
  respectiv.
* Daca programul tau face o mutare incorecta sau depaseste limita de timp
  va primi 0 puncte.
  Atentie: Numai procedura MyMove trebuie sa opreasca programul tau, nu-l
  opri fortat cand ajunge la 2 secunde.

Observatie:
^^^^^^^^^^^
* Deoarece pentru a va testa programul nu aveti acces la biblioteca NimLib
  va trebui sa va construiti una asemanatoare pe calculatorul dumneavoastra.
* Nu trimiteti si biblioteca dumneavoastra pentru evaluare, programul
  dumneavoastra va fi evaluat cu biblioteca evaluatorului.



                                     Valentin Gheorghita
                               UPB, Facultatea de calculatoare



                      PROBLEMA III
                      ^^^^^^^^^^^^

                   VINE MOS CRACIUN!....  ( 20 puncte )


  In tinutul inghetat, planurile pentru sfarsitul de An sunt deja facute.
Mos Craciun stie ce cadouri trebuie impartite copiilor. Intre drumurile pe
care le face si numarul de jucarii din sac exista o relatie bine definita.
Pentru a-l ajuta, sfetnicii mosului au realizat un tablou dreptunghiular
cu 100 linii si 100 coloane, avand 10.000 pioni. Piesele de pe tablou sunt
pionii ce au o fata colorata in negru si una in rosu. La inceput toti pionii
sunt cu fata neagra vizibila. Se stie ca inaintea plecarii la drum sfetnicii
intorc pionii astfel incat sa apara printr-un numar minim de intoarceri un
anumit numar de piese cu fata rosie vizibila. Numarul de intoarceri
reprezinta numarul de drumuri pe care le realizeaza Mos Craciun pentru a
da atatea jucarii cate piese rosii sunt pe tabla.

Regula generala:
^^^^^^^^^^^^^^^^
    Nu se poate intoarce un pion decat daca se intoarce in totalitate linia
(orizontala sau verticala) pe care se gaseste pionul.
            ^^^
Se pot intoarce toate liniile pe care le dorim, si de cate ori dorim.

Cerinta:
^^^^^^^^
    Dati numarul minim de intoarceri de linii (orizontale si verticale)
pentru a apare N pioni rosii pe tabla.

Fisierul de intrare:
^^^^^^^^^^^^^^^^^^^^
        -are pe fiecare linie cate un numar intreg
        -N1, N2,...,Nk reprezentand numarul de piese rosii
        (numarul de jucarii)
NOEL.IN:
N1
N2
....
Nk

Fisierul de iesire:
^^^^^^^^^^^^^^^^^^^
        -are pe fiecare linie cate un raspuns
        -P1, P2,...,Pk numarul minim de intoarceri de linii pentru a apare
         N1, N2,...Nk piese rosii; daca nu exista solutie se va scrie "NU".
NOEL.OUT:
P1
P2
....
Pk

Exemplu:
^^^^^^^^
NOEL.IN:                   NOEL.OUT:
1990                       43
1970                       NU

Timp de executie 1 sec/fiecare N.( 586/133Mhz.)

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



