
Motto: "Nu e de ajuns sa ai inteligenta, trebuie sa o folosesti bine."
                                               ( Descartes )


                        A FOST ODATA... - 30 puncte
                        ^^^^^^^^^^^^

Motto: "Quaevis comparatio claudicat"
        ("Orice comparatie isi are lipsurile ei")
                         Cicero, "De senectute"



.. si atunci mama cea vitrega i-a spus Cenusaresei:
"Iata, ai aici N<=10000 chip-uri VLSI, numerotate de la 1 la N.
Unele din ele sunt bune, dar altele sunt defecte. Sa faci bine sa le alegi
imediat pe cele bune de cele defecte, ca altfel ai incurcat-o !"
Apoi femeia cea haina pleca la balul printului impreuna cu fiicele ei.

Sarmana Cenusareasa se aseza intr-un colt si se porni pe plans. Cele N
chip-uri aratau exact la fel - cum putea sa le aleaga ? Dar in timp ce
plangea, zana buna aparu si ii darui un obiect ciudat. Apoi ii spuse:

"Draga mea Cenusareasa, fiindca esti buna la suflet, am sa te ajut si eu.
Iata aici un modul cu care poti testa chip-urile. Plasand oricare doua
chip-uri in acest modul, ele se vor testa unul pe celalalt.
Un chip bun iti va spune intotdeauna cu precizie daca chip-ul pereche este
bun sau defect.
In schimb, sa nu ai incredere in ceea ce iti va spune un chip defect. El
poate sa ofere informatii corecte despre chip-ul pereche sau poate sa minta.
Testand deci chip-urile A si B, iata ce concluzii poti trage:


Chip-ul A spune:          Chip-ul B spune         Concluzii
-----------------------------------------------------------------------------
"Chip-ul B este bun"     "Chip-ul A este bun"     Ambele chip-uri sunt bune
                                                   sau ambele sunt defecte
"Chip-ul B este bun"     "Chip-ul A este defect"  Cel putin un chip e defect
"Chip-ul B este defect"  "Chip-ul A este bun"     Cel putin un chip e defect
"Chip-ul B este defect"  "Chip-ul A este defect"  Cel putin un chip e defect
-----------------------------------------------------------------------------

Acest modul te va ajuta sa-ti termini treaba si sa pleci si tu la bal. Tine
minte insa doua lucruri.
In primul rand, sa stii ca mai mult de N/2 chip-uri sunt bune.
In al doilea rand, modulul se va arde dupa ce il vei folosi de 2*N ori.
Ai asadar grija sa nu irosesti testele. As mai sta sa te ajut, dar
trebuie sa ajung si eu la bal. Succes !". Si a disparut.

Fericita, Cenusareasa s-a dus drept la agenda ei telefonica si v-a sunat pe
dumneavoastra pentru a va ruga sa scrieti un program care sa o indrume in
activitatea de triere a chip-urilor. Cenusareasa va va comunica toate datele
de care aveti nevoie prin intermediul unui modul Pascal sau C. Modulul se va
include adaugand urmatoarea linie in codul sursa:

Pascal : uses Cindy;
C      : #include "cindy.h"

Modulul va pune la dispozitie urmatoarele proceduri si functii:

Pascal: procedure LoadData;
C     : void loaddata(void);
        Aceasta procedura se va executa o singura data, OBLIGATORIU inainte
        de apelarea oricarei alte proceduri din modul. Ea se ocupa de
        incarcarea datelor.

Pascal: function NChips:Integer;
C     : int nchips(void)
        Aceasta functie intoarce numarul N de chipuri.

Pascal: procedure Test(X,Y:Integer; var SayX, SayY:Integer);
C     : void test(int X, int Y, int *SayX, int*SayY);
        Aceasta procedura testeaza chip-urile cu numerele X si Y. Ea va
        intoarce valori in SayX si SayY, astfel:
        SayX=0 daca chip-ul X spune "Chip-ul Y este defect"
        SayX=1 daca chip-ul X spune "Chip-ul Y este bun"
        SayY=0 daca chip-ul Y spune "Chip-ul X este defect"
        SayY=1 daca chip-ul Y spune "Chip-ul X este bun"

Iata un exemplu Pascal de folosire a modulului:

program mingIsFun;
uses Cindy;
var N, A, B:Integer;
begin
  { ... alte instructiuni ... }
  LoadData;
  N:=NChips;
  Test(1, 2, A, B);
  if A*B=1
    then WriteLn('Chip-urile 1 si 2 sunt ambele bune sau ambele defecte')
    else WriteLn('Cel putin un chip dintre chip-urile 1 si 2 este defect');
  { ... alte instructiuni ... }
end.

Programul vostru trebuie sa scrie in fisierul:
 "CHIPS.TXT" N caractere "0" sau "1",
toate pe acelasi rand, nedespartite prin spatii. Nu se va adauga EOLN sau
vreo linie goala la sfarsitul fisierului (deci fisierul de iesire va avea
exact N octeti).
Primul caracter tiparit va fi 0 daca primul chip este defect sau 1 daca el
este bun.
Al doilea caracter tiparit va fi 0 daca al doilea chip este defect sau 1
daca el este bun, si asa mai departe. De exemplu,
succesiunea "1010110" inseamna ca chip-urile 1, 3, 5 si 6 sunt bune, iar
chip-urile 2, 4 si 7 sunt defecte.

TIMP LIMITA pentru un test: 2 secunde.

Alte precizari:
^^^^^^^^^^^^^^
1. Un test al programului nu se considera trecut daca depaseste 2*N folosiri
   ale modulului.
2. Nu se acorda punctaje partiale pentru etichetarea corecta numai a unei
   parti din chip-uri.
3. Nu se vor acorda puncte pentru programele care depasesc 2 secunde de
   executie. Se garanteaza ca timpul de executie al modulului "Cindy" este
   sub 0.1 secunde (prin "timpul de executie al modulului" se intelege timpul
   necesar pentru un apel al procedurii LoadData, un apel al functiei NChips
   si 20000 de apeluri ale procedurii Test).
4. Programele vor fi executate pe un procesor Cyrix P166+ cu 16MB RAM.
5. La executia programului, 500 kB din memoria de baza vor fi liberi.
6. Pentru a descuraja folosirea metodelor euristice, evaluarea se va face
   astfel: se vor rula 15 teste grupate in 5 seturi a cate 3 teste. Fiecare
   grupa va avea un punctaj al ei, care se va acorda numai daca toate cele 3
   teste componente ale grupei au fost trecute.
7. Trimiteti un e-mail la cfrancu@pcnet.pcnet.ro pentru alte intrebari.
                          ^^^^^^^^^^^^^^^^^^^^^^


+------------------------+------------------------------------------+
|     Catalin Francu     | "I've got nothing to do today but smile" |
| cfrancu@pcnet.pcnet.ro |                  (Simon & Garfunkel)     |
+------------------------+------------------------------------------+





                    COLONII PE MARTE...  - 25 puncte
                    ^^^^^^^^^^^^^^^^

       In anul 2003, pe planeta Marte s-a terminat constructia unei "oaze",
in care viata oamenilor putea fi posibila.
In vederea colonizarii, fiecare tara de pe glob, a trimis un reprezentant.
Stiind ca, pentru a transporta un individ se foloseste cate un avion special
si ca fiecare deplasare are un cost bine stabilit dat intr-o matrice,
de forma:

      C[i,j] = costul transportului persoanei "i", folosind avionul "j",

se cere sa se determine o repartitie a persoanelor pe avioane, astfel incat
costul total de transport sa fie minim.
                                 ^^^^^

Cerinte:
^^^^^^^
Datele de intrare se citesc din fisierul MARTE.IN, avand structura:

n                        // pe prima linie numarul de indivizi;
c   c   c   ... c
 11  12  13      1n
                         // pe urmatoarele n linii costurile corespunzatoare
c   c   c   ... c        // deplasarilor, numere naturale cuprinse intre
 21  22  23      2n      // 1 si 255, separate prin spatiu;
                         // 0 < n < 1000;
...................
c   c   c   ... c
 n1  n2  n3      nn

Datele de iesire se scriu in fisierul MARTE.OUT, avand structura:

c                       // reprezentand pe primele n linii costurile
 1 i1                   // c       1 < k < n;    1 < ik < n
c                           k ik
 2 i2                   // ce realizeaza minimul cerut, precum si
c                       // pe ultima linie valoarea acestui minim
 3 i3                                                       ^^^^^
....                   // min = c     + c     + ... + c
c                                 1 i1    2 i2          n in
 n in
min

Exemplu:
^^^^^^^
MARTE.IN:                                 MARTE.OUT:

6                                         27
17 43 27 14 39 52                         13
29 24 69 90 23 13                         16
18 90 62 12 16 70                         14
58 14 6 18 73 64                          15
15 41 38 36 40 60                         18
25 44 18 44 13 50                         103

Timpul de executie maxim 3 sec/test, pentru 586/133MHz.

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




                     DIN NOU ZEROURI...   - 20 puncte
                     ^^^^^^^^^^^^^^^

      Fie numerele naturale, scrise unul dupa celalalt, de la 1 la n,
n citit din fisierul Z.IN, n avand maxim 1000 de cifre.
      De cate ori apare cifra zero in scrierea acestor numere?
Numarul cifrelor de zero se va scrie in fisierul Z.OUT.


Example:
^^^^^^^
Z.IN:                            Z.OUT:
123456                           58985

Z.IN:                            Z.OUT:
222222222                        175308642

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


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

