BISTRITA-NASAUD, 28.02.1995, CLASA A IX-A

     1. Se considera un grup de N persoane, avand fiecare un anumit nr. de
preocupari, cel mult p preocupari. Preocuparile sunt codificate prin nu-
mere reale (eventual intregi) nenule.
35p. a)Sa se determine perechile de persoane care au preocupari comune,
specificand pentru fiecare astfel de pereche numarul de preocupari comune;
35p. b)Sa se determine perechea, eventual perechile, de persoane cu un nu-
mar maxim de preocupari comune;
30p. c)Sa se determine preocuparea imbratisata de un nr. maxim de persoane.

100p.2. O veche legenda chinezeasca spune ca in Taramul Invatatilor se afla
un intelept care inmulteste nr.naturale dupa reguli numai de el stiute.
Odata, intrebat care este produsul dintre 49 si 357, el a desenat diagrama
urmatoare:           4         9
                |---------|---------|
                |  1  /   |  2  /   | 3
                |    /  2 |    /  7 |
                |---------|---------|
                |  2  /   |  4  /   | 5
                |    /  0 |    /  5 |
                |---------|---------|
                |  2  /   |  6  /   | 7
                |    /  8 |    /  3 |
                |---------|---------|
si a raspuns imediat ca rezultatul este 17493. Pe patul de moarte el a im-
partasit ucenicilor secretul sau:
- deasupra si in dreapta diagramei  se trec numerele care se inmultesc.
-se inmultesc perechile de cifre, trecandu-se unitatile in triunghiul de
jos si zecile in triunghiul de sus.
- se aduna apoi cifrele aflate in triunghiurile fiecarei diagonale SV-NE,
incepand cu extrema dreapta-jos a diagramei; cifra unitatilor sumei rezul-
tate este inscrisa sub diagrama, iar cifra zecilor este adaugata la triun-
ghiul aflat imediat deasupra.
 Pentru exemplul considerat obtinem succesiv:
          4         9                 4         9
     |---------|---------|        |---------|---------|
     |  1  /   |  2  /   | 3      |  1  /   |  2  /   | 3
     |    /  2 |    /  7 |        |    /  2 |    /  7 |
     |---------|---------|        |---------|---------|
     |  2  /   |  4  /   | 5      |  2  /   |  4  /   | 5
     |    /  0 |    /  5 |        |    /  0 |    /  5 |
     |---------|---------|        |---------|---------|
     |  2  /   |  6  /   | 7      |  3  /   |  6  /   | 7
     |    /  8 |    /  3 |        |    /  8 |    /  3 |
     |---------|---------|        |---------|---------|
                    3

          4         9                 4         9
     |---------|---------|        |---------|---------|
     |  1  /   |  2  /   | 3    1 |  1  /   |  2  /   | 3
     |    /  2 |    /  7 |        |    /  2 |    /  7 |
     |---------|---------|        |---------|---------|
  7  |  3  /   |  4  /   | 5    7 |  3  /   |  4  /   | 5
     |    /  0 |    /  5 |        |    /  0 |    /  5 |
     |---------|---------|        |---------|---------|
  4  |  3  /   |  6  /   | 7    4 |  3  /   |  6  /   | 7
     |    /  8 |    /  3 |        |    /  8 |    /  3 |
     |---------|---------|        |---------|---------|
          9         3                  9         3
          Se cere sa se scrie un algoritm care calculeaza produsul a doua
numere naturale folosind algoritmul de mai sus.


BRASOV, 19.02.1995, CLASA A IX-A

Proba teoretica:
    1.Se considera matricea A de n (0 <= n <= 100) linii si coloane ale
carei elemente sunt numere intregi; pentru n=7 avem urmatoarea matrice:
               1  1  1  1  1  1  1
               1  1  2  3  4  5  6
               1  2  1  3  6 10 15
               1  3  3  1  4 10 20
               1  4  6  4  1  5 15
               1  5 10 10  5  1  6
               1  6 15 20 15  6  1

    a)Gasiti regula dupa care sunt generate elementele matricei. Ca exem-
plu, completati matricea data cu urmatoarele doua linii si coloane.
    b)Folosind matricea de la punctul a), scrieti un program Pascal care
citeste numerele intregi n, i, j (10 <= n <= 100, 1 <= i <= n, 1 <= j <=n),
determina si afiseaza A[i,j].

    2.Sa se scrie un program Pascal care calculeaza:
              ___  n          ___  n
       ( 2 - V 3  )  + ( 2 + V 3  ) fara a utiliza tipul REAL.
Timp de lucru 3 ore.

Proba practica:
    1.Se considera o clasa de n ( n <= 40 ) elevi intre care exista relatii
de simpatie, nu neaparat reciproce. Sa sa elaboreze un program Pascal
pentru a forma grupuri de elevi intre care exista relatii de prietenie
reciproca. Un elev nu poate sa apartina mai multor grupuri.
   Intrarea se va preciza astfel:
 n   - numarul de elevi;
 i j - elevul j este simpatizat de elevul i;
 ...
 0 0 -pentru a marca sfarsitul introducerii datelor.

   2.Se considera un sir ordonat de cel mult 10000 de numere intregi pozi-
tive distincte. Se cere sa se determine cate perechi de numere a caror suma
este 999999 sunt in sir, efctuand un nr.minim de comparatii.

CARAS-SEVERIN, 04.03.1995, CLASA A IX-A

 1. Un candidat la presedentie aflat in turneu electoral viziteaza cele N
(dat) judete ale tarii in M (dat) zile. Se da numarul de judete vizitate in
fiecare zi.
    Se cere sa se arate ca exista un interval de zile consecutive in care
viziteaza exact 2*M-N-1 judete, daca acest numar este pozitiv.

 2. Se da un vocabular de litere V si cuvintele care se formeaza dupa urma-
toarele reguli:
- se dau doua multimi I si O ale lui V astfel incat orice cuvant care ince-
pe cu o litera din I si se termina cu o litera din O
- pentru orice litera "a" din V se dau literele care pot urma dupa ea
intr-un cuvant (imediat pe urmatoarea pozitie).
    Sa se numere si sa se afiseze cate cuvinte de patru litere exista si sa
se afiseze.
EXEMPLU:
        V={A,B,C,D,E,F,M,N,R,T,V}
        I={A,E,N}
        O={A,C,D}
        Succesori pentru A {C,E,F,N,T}
        Succesori pentru C {A,D,.....} se citesc
        Succesori pentru E {D,N,.....}
        ..............................
        Un cuvant de trei litere : ACA - C este succesor pentru A,
                                         A este succesor pentru C,
                                         A apartine lui I, A apartine lui O.
        Un cuvant de patru litere: AECD.


CALARASI, CLASA A IX-A

 Proba teoretica:
 1. Se citeste un text de la consola. Stiind ca cuvintele sunt separate
prin spatiu, virgula sau punct si virgula, iar propozitiile prin punct,
sa se afiseze la consola toate propozitiile din text, apoi toate cuvintele
utilizte si numarul de aparitii in text.

 2. Fie o propozitie scrisa in limba pasareasca. Stiind ca un cuvant in
limba pasareasca se formeaza dupa urmatoarea regula: vocala-litera P-vocala
de exemplu: TURC --> TUPURC
a) sa se traduca in limba romana propozitia:
   IPINVAPATAPAM TOPOAPATAPA VIPIAPATAPA
b) sa se traduca in limba pasareasca orice propozitie tastata de la consola.

 Proba practica:
 1. Un taran doreste sa treaca un lup, o capra si o varza de pe malul stang
pe malul drept al unui rau. Stiind ca in barca nu se pot transporta decat
doua elemente dintre om, lup, capra, varza, sa se scrie un program care re-
zolva problema taranului.

 2. Dandu-se un numar b scris in binar, intreg, sa se realizeze un algoritm
care genereaza:
a) toate secventele b1, b2, ... bm astfel incat b1 * b2 * .. * bm = b;
b) toate secventele de numere intregi z1, z2, ... zl astfel incat z1 * z2 *
*.. * zl = z, unde z este echivalentul numarului b scris in baza 10.


CLUJ, 18.02.1995, CLASA A IX-A
Proba teoretica:
 1. La impartirea diamantelor furate de hotii lui Ali-Baba, fiecare hot are
notat numarul de diamante furate de el. Din acest numar hotul poate sa taie
(sa elimine) k cifre. Cifrele se pot elimina de oriunde din numar si nu
trebuie sa fie neaparat consecutive. Numarul obtinut dupa eliminarea celor
k cifre reprezinta numarul diamantelor ce revin sefului Ali-Baba din prada
respectivului hot.
    Sa se scrie un program care, cunoscand numarul n de diamante furate de
un hot si numarul k, poate determina numarul minim de diamante care trebuie
predate lui Ali-Baba de catre hotul respectiv.
Observatie:
           Validarea datelor de intrare este obligatorie, stiind ca:
           - numarul natural, nenul, n se da sub forma unui string de cel
             mult 40 de caractere;
           - numarul k este un intreg nenegativ strict mai mic decat numarul
             cifrelor lui n.
Exemple:     Daca n=21789 si k=2, atunci rezultatul este 178.
             Daca n=  901 si k=1, atunci rezultatul este 01 sau 1.

 2. Se da un tablou bidimensional cu m linii si n coloane, avand ca elemente
cifre din baza zece. Sa se listeze liniile din acest tablou care au caracter
de palindrom (vom spune ca o linie are caracter de palindrom daca parcursa
de la dreapta la stanga se obtine aceeasi succesiune de cifre ca la parcur-
gerea de la stanga la dreapta).
Exemple de linii cu caracter de palindrom
        - pentru n=5:    8 5 6 5 8;
        - pentru n=6:    4 3 7 7 3 4.

Proba practica:
 1. Se considera segmentul [0,1) care se imparte in cinci intervale egale.
Se elimina trei cincimi de la mijlocul intervalului, sub forma unui inter-
val inchis la stanga si deschis la dreapta, adica se elimina intervalul
[ 1/5 , 4/5 ). Pentru fiecare dintre segmentele ramase se elimina din nou
trei cincimi de la mijlocul segmentelor, tot sub forma unor intervale
inchise la stanga si deschise la dreapta, adica se elimina intervalele
[ 1/25 , 4/25 ) si [ 21/25 , 24/25 ). Operatia descrisa mai sus se repeta
de un numar oricat de mare de ori.
    Sa se scrie un program care, fiind date numerele naturale p si q cu
0 < p/q < 1, sa se determine daca p/q apartine unui interval eliminat sau nu.

 2. Fie n <= 3000 un numar natural. Se cere sa se determine un multiplu al
sau in a carui scriere in baza 10 sa intervina numai cifrele 0 si 1.


CONSTANTA, CLASA A IX-A

 1. Se considera expresia:
              2             2^2             2^3
 E(x) = 1 - ----- * x^1 + ------- * x^2 - ------- * x^3 + .....
            3 * 2         3^2 * 3         3^3 * 4

         (-1)^n * 2^n
      + -------------- * x^n  , n numar natural.
          3^n * (n+1)
 Sa se calculeze valoarea expresiei E(x) in doua moduri astfel incat sa
obtinem doua rezultate diferite. Justificati raspunsul.

 2. Sa se genereze toate numerele patrate perfecte mai mici decat un numar
natural n dat, fara a folosi functii predefinite de ridicare la putere.

 3. a) Sa se arate ca orice fractie m/n cu m,n numere naturale nenule si
0 < m/n < 1 poate fi scrisa sub forma: m/n = 1/q1 + 1/q2 +...+ 1/qr cu
0< q1 < q2 < .. < qr numere naturale si qk-1 | qk, oricare k intre 2 si r.
    b) Sa se elaboreze algoritmul si programul Pascal.

HUNEDOARA, CLASA A IX-A

Proba teoretica:
 1. Se da o multime A={a1,a2,...,an} avand elementele numere naturale si
functia f : A-->N astfel: pentru fiecare x din A, f(x) este ultima cifra a
numarului 7^x. Scrieti programul ce determina codomeniul functiei f, adica
multimea f(A).

 2. Se dau doi vectori A[1..M] si B[1..N]. Sa se scrie programul care sa
verifice daca toate componentele vectorului A luate in orice ordine se ga-
sesc in vectorul B pe pozitii consecutive. Daca exista astfel de situatii sa
se afiseze fiecare pozitie din vectorul B unde incepe secventa de elemente
din A.

Proba practica:
 1. Fie variabilele logice V1, V2,...,Vn. Atasam fiecarui numar natural X
o formula logica in felul urmator:
- se considera B1, B2,..., B8 primele 8 cifre, cele mai semnificative din
reprezentarea binara a lui X;
- pentru fiecare pozitie I intre 1 si 8 se include in formula variabila Vi
daca si numai daca Bi=1;
- varibilele din formula se leaga prin conjunctie (and).
Afirmam ca o formula (conditie) logica C este mai generala decat formula D
daca D este adevarata ori de cate ori C este adevarata. Numarului 0 i se
asociaza formula logica falsa.
     Dandu-se N numere naturale, sa se determine o formula continand un
numar minim de variabile Vi, mai generala dacat toate formulele corespunza-
toare celor n numere date.

 2. Fie V={0,1}. Fie X=x1x2...xn cu n>=1 dat si xi apartine lui V pentru
orice i in multimea {1,2,...,n}. Se mai dau K si S in multimea {1,2,...,n}.
a) Sa se genereze toate cuvintele Y=y1y2...yk cu yi apartine lui V pentru
orice i in multimea {1,2,...,k} si y1+y2+...+yk=S
b) Sa se determine pentru fiecare dintre cuvintele Y generate la a) de cate
ori apar ca subcuvinte ale lui X.

IALOMITA, CLASA A IX-A

 1. Fie M urmatoarea multime:
-1 apartine lui M ;
-daca x apartine lui M, 2x si 3x apartin lui M.
    Sa se afiseze primele k elemente ale multimii M (k >= 0, dat) in ordine
crescatoare.
EXEMPLU: K=6    M={1,2,3,4,6,8}

 2. Se considera un recipient cu o capacitate C, numar intreg si pozitiv.
Avand la dispozitie n vase (n>0, dat), de capacitati l1,l2,...,ln, intregi
si distincte date, sa se determine o modalitate de umplere a recipientului
folosind cele n vase.
Observatie: un vas e folosit la intreaga lui capaciatate. Daca problema nu
are solutie, sa se afiseze un mesaj corespunzator.
EXEMPLU:
  C=237
  N=9
  V=(7,4,2,100,5,10,9,8,3)
  Iesire:
  1 --> 6 x 7
  2 --> 7 x 4
  3 --> 1 x 2
  4 --> 1 x 100
  6 --> 2 x 10
  7 --> 5 x 9
  cu semnificatia: vasul 1 se foloseste de 6 ori, etc.


MEHEDINTI, CLASA A IX-A

 1. La o tragere expres speciala se extrag M numere distincte din multimea
{1,2,3,...,N}, N>=6 . O persoana a jucat la acest joc extragand K numere
distincte din cele N posibilitati, 5 <= k <= M. Numerele N,M,K se citesc de
la tastatura. De asemenea se dau de la tastatura numerele extrase oficial,
in ordinea in care au fost extrase, precum si cele alese de persoana.
Categoriile de castig sunt urmatoarele:
categoria 1: K numere din primele K extrase oficial;
categoria 2: K numere din toate cele M extrase oficial;
categoria 3: K-1 numere din primele K-1 extrase oficial;
categoria 4: K-1 numere din primele K extrase oficial;
categoria 5: K-1 numere din toate cele M extrase oficial;
categoria 6: K-2 numere din toate cele M extrase oficial.
   Sa se afiseze un mesaj daca persoana a castigat sau nu precizandu-se
categoria de castig maxim unde se incadreaza (categoria 1 produce castigul
cel mai mare, iar categoria 6 produce castigul cel mai mic).
Exemplu pentru N=55, M=6, K=5
 Numerele extrase oficial sunt {1,2,3,4,5,6}
-Daca numerele alese de persoana sunt {5,4,3,2,1} pe ecran se va afisa:
      CASTIGATOR, CATEGORIA 1;
-Daca numerele alese de persoana sunt {9,1,5,3,2} pe ecran se va afisa:
      CASTIGATOR, CATEGORIA 4;
-Daca numerele alese de persoana sunt {2,4,5,8,9} pe ecran se va afisa:
      NECASTIGATOR.

 2. Se da o matrice patratica de ordinul N (N>=3, impar). Parcurgand matri-
cea ca in figura de mai jos se obtin doi vectori:
-V1 parcurgand matricea pe traseul AOC;
-V2 parcurgand matricea pe traseul BOD;

    A---------B
    |\       /|
    | \     / |
    |  \   /  |
    |   \O/   |
    |   / \   |
    |  /   \  |
    | /     \ |
    |/       \|
    C---------D
Vectorul V2 se aseaza in continuarea lui V1 astfel incat extremitatea finala
a lui V1 este inaintea extremitatii initiale a lui V2. Vectorul V2 se depla-
seaza de la dreapta la stanga pana cand doua secvente (una din V1, alta din
V2) din zona de suprapunere, de aceeasi lungime, au valorile extremitatilor
respectiv identice prin suprapunere.
   Daca exista sa se afiseze secventele respective, in caz contrar sa se afi-
seze un mesaj corespunzator.
EXEMPLU (incoerent!) : ( 7 8 9 5 2 1 7 8 5 3 9)
                            (1 1 2 5 3 8 7 6 2 1 9)
CONTREXEMPLU (IDEM)  : ( 7 8 9 5 2 1 7 8 5 3 9)
                            (1 1 8 5 3 2 7 6 2 1 9)


PRAHOVA, 11.02.1995, CLASA A IX-A

 1. Fie S={A1,A2,...,A2n} o multime de 2n puncte astfel incat oricare trei
nu sunt coliniare. Sa se afiseze o multime S' de segmente cu capete in pun-
ctele din S, cu numar maxim de elemente posibil, astfel incat oricare trei
segmente din S nu formeaza triunghi.
         EXEMPLU:
Intrare: n=4
         S={1,2,3,4,5,6,7,8}    (???)
Iesire : S'={(1,2),(1,3),...}

 2. Fie S={s1,s2,s3} o multime de trei simboluri.
   i) Sa se genereze multimea V={e1,e2,...} ale carei elemente se formeaza
dupa urmatoarele reguli:
-orice simbol din S este element din V;
-daca ei si ej sunt elemente din V, atunci eiej este tot element din V;
-elementele din V au cel mult N simboluri si fiecare element poate contine
de cel mult NS1 ori simbolul s1, NS2 ori simbolul s2, NS3 ori simbolul s3,
pentru N,NS1,NS2,NS3 (NS1+NS2+NS3=N) valori date .
   ii) ignorand conditia c) din definitia multimii V sa se realizeze o codi-
ficare a numerelor naturale cu simboluri din multimea S.
Exemplu pentru punctul i)
Intrare: N=2, NS1=1, NS2=1, NS3=0
Iesire : V={s1,s2,s1s2,s2s1}

 3. Se da un tablou triunghiular cu componente numere naturale, de N linii.
Se considera ca fiind un drum o insiruire de componente ale triunghiului cu
proprietatea ca oricare componenta a drumului va fi urmata in aceasta insi-
ruire de componenta din triunghi aflata fie pe linia urmatoare si pe aceeasi
coloana, fie pe linia urmatoare si pe coloana urmatoare (Aij va fi urmat fie
de Ai+1j fie de Ai+1j+1).
    Sa se afiseze toate drumurile care au proprietatea ca suma componentelor
sale este maxima.
EXEMPLU:
Intrare: n=4
1
2 7
4 3 10
0 3 4 1
Iesire:
1 7 100 4


TIMIS, CLASA A IX-A

 1. Se considera un tablou bidimensional ale carui elemente sunt numere
intregi sau expresii simple in care pot sa apara ca operatori + si -, iar
ca operanzi numere intregi si elemente ale tabloului bidimensional conside-
rat. Expresiile se evalueza de la stanga la dreapta.
    Sa se scrie un program care calculeaza elementele unui astfel de tablou
(cele care nu pot fi calculate vor primi ca valoare un spatiu):
-pe prima linie se dau doua nr., reprezentand nr.de linii,respectiv de co-
loane ale tabloului considerat;
-pe urmatoarele linii sunt date elementele tabloului, cate unul pe linie.
EXEMPLU:pentru setul de date de intrare
2 3
1
a[1,1]+3
a[2,2]-4+a[1,2]
3-4+10
a[1,3]+1
-a[2,1]
iesirea este:
1   4
9       -9

VALCEA, CALSA A IX-a

 1. Un taran pus pe glume, ofera spre vanzare un numar de n produse. El a
facut un mic calcul si a determinat, pentru fiecare cantitate din produsele
oferite spre vanzare, numarul de calorii pe care le contine intrega cantitate
din produlsul respectiv. Taranul a scris pe cate o eticheta numerele astfel
determinate si a pus fiecare eticheta langa produsul corespunzator avand
grija ca dupa fiecare vanzare sa corecteze in mod corespunzator nuamrul
inscris pe eticheta.
   O gospodina ce dispune de o anumita suma de bani pentru cumparaturi, do-
reste sa cumpere produse de la acel taran astfel incat sa cheltuiasca in-
treaga suma de care dispune dar sa duca acasa cat mai multe calorii. Gospo-
dinei ii e indiferent ce produse cumpara si in ce cantitati, scopul fiind ca
produsele cumparate sa contina in totalitate cel mai mare numar de calorii.
   Determinati cat a cumparat gospodina din cele n produse.
   Datele de intrare vor fi introduse de la tastatura in felul urmator:
-pe prima linie va fi introdus numarul de produse (n);
-pe urmatoarele n linii vor fi introduse cate doua valori reprezentand numa-
rul de calorii determinat de taran pentru fiecare produs si cat costa in-
treaga cantitate din produsul respectiv;
-pe ultima linie (a n+2-a) va fi introdusa suma de care dispune gospodina
pentru cumparaturi.
   Datele de iesire vor fi afisate pe doua linii astfel:
-pe prima linie vor fi afisate numerele de la 1 la n reprezentand numarul
produsului;
-pe cea de-a doua linie vor fi afisate, sub numerele corespunzatoare, frac-
tiunile cumparate de gospodina din produsul respectiv.

 2. Fiind dat un numar real a, sa se afle daca el se afla printre primele
elemente ale unui sir de numere reale a[i], i=1,2,...,n si, in cazul in
care el se afla printre acele numere, sa se afle care ar fi pozitia sa in
sirul ordonat a[i], dar fara a ordona sirul a[i] si fara a folosi un alt sir
de numere.
   Datele de intrare vor fi introduse de la tastatura in felul urmator:
-pe prima linie vor fi introduse valoarea numarului a si numarul n de ele-
mente ale sirului;
-pe urmatoarea linie vor fi introduse cele n elemente ale sirului.
   Datele de iesire vor fi afisate pe cel mult doua linii astfel:
-pe prima linie va fi afisat unul din mesajele:
"Numarul se afla in sirul dat, in sirul ordonat ocupand pozitia:"
"Numarul nu se afla in sir"
-in situatia in care numarul se afla in sir, pe a doua linie va fi afisat
indicele sau.