
Motto: " E.I.C.-ul a fost ca o cutie de bomboane de ciocolata - am deschis-o,
        nestiind ce vom gasi in ea..."
                           Adaptat dupa "Invataturile lui Forrest Gump."





                      UN ALT FEL DE RUBIK  -  80 puncte
                      ^^^^^^^^^^^^^^^^^^^


    Se considera o placa dreptunghiulara de dimensiuni m x n
(3 <= m,n <= 100) n care fiecare element consta intr-un ecran cu cristale
lichide si un comutator care se roteste, ale carui sensuri de rotatie sunt
marcate cu "+" si "-".

    Initial fiecare din cele m x n ecrane ale placii are listat cate un
numar intreg pozitiv. O miscare a comutatorului unui element are ca efect
modificarea valorilor scrise atat pe ecranul corespunzator elementului,
cat si pe ecranele elementelor vecine pe linie si coloana (daca exista).
Modificarea consta in adunarea cu 1 (daca comutatorul s-a rotit in directia
marcata cu +) respectiv cu -1 (la rotirea in directia marcata cu -) a
valorilor aflate pe ecranele implicate.

Exemplu, la o placa de forma:
^^^^^^^
            5 2 1 3 8
            6 8 1 2 2
            4 6 5 2 9

rotirea spre "+" a comutatorului elementului din pozitia (2,3) conduce
la tabloul:

                        5 2 2 3 8
            6 9 2 3 2
            4 6 6 2 9

iar apoi, dupa rotirea spre "-" a comutatorului elementului din pozitia (1,4)
se obtine tabloul:

            5 2 1 2 7
            6 9 2 2 2
            4 6 6 2 9

Cerinte:
^^^^^^^
   Fiind data o astfel de placa si o valoare intreaga x din [0,99], sa se
descrie secventa de miscari care sa conduca la o placa in care toate
elementele au listate pe ecran aceeasi valoare x.

Intrare:
^^^^^^^
Fisierul de intrare RUBIK.IN are forma:

m n x           - m,n - dimensiunile tabloului, x - valoarea finala
a   a   .. a
 11  12     1n
a   a   .. a        - configuratia initiala a tabloului
 21  22     2n        (pe o linie numerele sunt separate prin cate un
                           spatiu)
......
a   a   .. a
 m1  m2     mn


Iesire:
^^^^^^
Pentru fiecare set de date de intrare, fisierul de iesire RUBIK.OUT va avea
structura:

k               - numarul de mutari
p  i  j         - (i ,j ) sunt coordonatele comutatorului activat la
 1  1  1                    s  s
p  i  j                   mutarea s;
 2  2  2                  p  are una din valorile "+" sau "-" (1 <= s <= k);
....                      s
p  i  j
 k  k  k

Observatie:
^^^^^^^^^^
 - verificarea se va face astfel incat pentru o secventa de mutari, scrisa in
fisierul RUBIK.OUT, se vor genera mutarile pentru a se vedea daca ele conduc
la o solutie.

Exemplu:
^^^^^^^^
RUBIK.IN:                              RUBIK.OUT:

4 4 2                                  5
2 3 2 3                                + 2 3
3 2 2 2                                - 4 4
3 3 1 3                                - 1 4
3 3 3 3                                - 4 1
                                       - 2 2


----------------------------------------------------------------------------
   Problema a fost propusa la pregatirea lotului de informatica de un
   colectiv de profesori: prof. Adrian Atanasiu, prof. Serban Marinel
   si prof. Maria Nita.
   Problema are un punctaj mare, deoarece avem o solutie partiala.
   Verificatorul este realizat, algoritm teoretic pentru rearanjarea
   matricei exista si testele pentru verificare sunt corecte, dar nu
   avem solutie Pascal si nici nu am primit in perioada de pregatire
   a lotului. Deci in cazul unui esec (nici o solutie cu punctaj maxim)
   nu va putem da un exemplu de problema bine realizata.
   Va multumim.
-----------------------------------------------------------------------------



                        CODIFICARI  -  20 puncte
                        ^^^^^^^^^^


      La sfarsitul concursului prin Internet, participantii au descoperit o
harta ce contine un mesaj codificat. Orice codificare are doua parti.
O prima parte contine caracterele mesajului iar partea a doua contine
reprezentarea codificata a mesajului. Acelasi caracter al mesajului se poate
repeta de mai multe ori.
Secventa de chei care codifica mesajul este:

  0, 00, 01, 10, 000, 001, 010, 011, 100, 101, 110, 0000, 0001, 0010,...

Secventa de chei are semnificatia:
  0  corespunde primului caracter;
 00  corespunde celui de-al doilea caracter....

Exemplu:
^^^^^^^
  MA MA#MIA
   0 corespunde lui M
  00 corespunde lui A
  01 corespunde caracterului spatiu ' '
  10 corespunde celui de-al doilea M .....

Codificarea fiecarui mesaj, care contine doar cifre de 0 si 1 se realizeaza
prin segmente, fiecare segment avand structura:
 - primele trei cifre reprezinta scrierea binara asociata lungimii n a cheilor
   din segment ;
 - urmatoarele cate n cifre binare reprezinta cheile caracterelor codificate;
 - un segment se termina cu o secventa binara formata doar din n cifre de 1.
Segmentele care reprezinta codificarea pot fi scrise pe mai multe linii, in
fisierul de intrare, enter-ul nefiind luat in consideratie.

Cerinte:
^^^^^^^
 - datele de intrare se citesc din fisierul COD.IN, cu structura:
 1).- pe prima linie textul codificat;
 2).- pe urmatoarele k linii codificarea ( k nedeterminat);
 3).- codificarea se termina cu grupul de cifre binare 000.
 - 1). 2). 3). se pot repeta de x ori.

 - datele de iesire se scriu in fisierul COD.OUT, cu structura:
    - pe x linii textele obtinute prin decodificare.


Exemplu:
^^^^^^^
COD.IN:
^^^^^^^
ECO IKUT
00101011000111010
00100111011001111000
NUSBECOT
0100100110110010010001110100111000

COD.OUT:
^^^^^^^^
EIC OK
SUCCES


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






                      TRIUNGHIURI   - 20 puncte
                      ^^^^^^^^^^^

     In plan se considera n puncte date prin coordonate numere intregi,
           n <= 1000.
     Trei puncte necoliniare determina un triunghi.

Cerinte:
^^^^^^^^
  Datele de intrare se citesc din fisierul ARIE.IN, cu structura:

n                    // reprezentand numarul de puncte existente in plan;
a  b
 1  1                // pe urmatoarele n linii se dau coordonatele
a  b                      punctelor din plan, separate prin spatiu;
 2  2
.....
a  b
 n  n

  Datele de iesire se scriu in fisierul ARIE.OUT, cu structura:

a  b  a  b  a  b     // reprezentand coordonatele punctelor care formeaza
 i  i  j  j  k  k       un triunghi de arie minima.


Observatie:
^^^^^^^^^^^
 Daca exista mai multe puncte distincte care determina triunghiuri de arii
egale, atunci acestea sunt scrise, toate, pe linii diferite.

Exemplu:
^^^^^^^^
ARIE.IN:                  fisierul      ARIE.OUT:

4                                       -2 4 2 2 4 2
2 2
4 2
-3 -1
-2 4

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

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

