                        CLASA a-IX-a



            PROBLEMA 1.
            Numere consecutive

    Sa se afiseze toate descompunerilele posibile ale numarului n
(n<=maxlongint) ca suma de numere naturale consecutive si sa se afiseze
si numarul de astfel de descompuneri.

Ex:
Intrare : n=15
Iesire  : 7 8
          4 5 6
          1 2 3 4 5

          Nr=3

            PROBLEMA 2.
             Permutare

    Se dau doua cuvinte de lungime n(n<=20000).
Sa se decida daca cel de-al doilea cuvint este o permutare circulara
a primului.

Ex1: Intrare :
     n=5  sir1=abcde sir2=deabc
     Iesire  : DA

Ex2: Intrare :
     n=5   sir1=abcde  sir2=cdacb
     Iesire  : NU

Ex3 :Intrare :
     n=10  sir1=abdcadaabb  sir2=abbabdcada
     Iesire  : DA

                 Problema 3.

                   GAURI

Se considera o tabla impartita in linii si coloane(n linii si m coloane)
ce contine  un numar de p piese, date prin coordonatele pozitiilor si
un numar de g gauri date de asemenea prin coordonate.
Se doreste eliminarea pieselor de pe tabla prin gaurile date folosind mutari
care respecta conditiile:
1)-Piesa se deplaseaza numai pe orizontala o singura casuta;
2)-Piesa se deplaseaza numai pe verticala o singura casuta;
Observatie:
a)Piesa poate folosi o deplasare combinata pe vericala si orizontala
(orizontala sau verticala)sub forma de L sarind din casuta in casuta.
b)Piesa pe drumul spre gaura nu trebuie sa sara peste o piesa deja existenta.
Cerinta: Alcatuiti un program care determina secventa minima de mutari prin
care sunt eliminate toate piesele de pe tabla respectand conditiile impuse.
Lungimea drumului catre o gaura a unei piese este numarul casutelor prin
care trece piesa.
Dimensiuni:
1<=n<=100
1<=m<=100
Afisarea va respecta formatul:
-Se afiseaza numarul natural q reprezentand suma minima a lungimilor
drumurilor pieselor catre gauri.
-Pe urmatoarele p linii se vor afisa numerele (i,j) (k,l) u
cu semnificatia piesa de pe pozitia (i,j) se elimina prin gaura de coordonate
(k,l) sarind prin u casute(ordinea afisarii reprezinta ordinea eliminarii
pieselor)
In cazul in care exista mai multe solutii de aceeasi lungime minima se va
afisa una singura.

Exemplu:
Pentru intrarea facuta de la tastatura:
n=6
m=7
Numarul de piese=4
Numarul de gauri=2
Piese pe pozitiile:
1 1
1 2
2 5
5 1
Gauri pe pozitiile:
3 3
4 6
Se va afisa pe ecran:
14
(1,2) (3,3) 3
(1,1) (3,3) 4
(2,5) (3,3) 3
(5,1) (3,3) 4
Timp de rulare per test 1 minut

                   Clasa a X-a
                            PROBLEMA 1

                       Expresie ne-buclucasa

    Se considera o expresie formata din numere naturale
inchise in paranteze drepte succesive (in mod corect)
Sa se afiseze valoarea corespunzatoare expresiei date,
conform regulilor de calcul:
1.-inchiderea intre paranteze a unei subexpresii corespunde la aplicarea
impartirii intregi a valorii subexpresiei la 2
2.-alaturarea a doua grupuri de paranteze semnifica aplicarea adunarii
valorilor corespunzatoare celor doua subexpresii.


Ex1 : [[[100]][5]] valoarea :13
Ex2 : [5][[[30]]] valoarea :5
Ex3 : [[20][30][[1]]] valoarea :12

Intrare : fisierul input.txt contine pe o singura linie
         expresia data.
Iesire  : Pe ecran valoarea expresiei.


                              PROBLEMA 2

                            Arbore generat

        Fie sirul asociat varfurilor unui arbore binar ce contine,pentru
fiecare varf in parte,numarul tuturor descendentilor sai din subarborele
stang si subarborele drept.Sa se genereze un arbore binar corespunzator
sirului dat si sa se afiseze acest arbore in preordine,sub forma indentata
astfel incat nodurile de pe acelasi nivel in arbore se regasesc pe aceeasi
coloana.
        Exemplu:
        Intrare: -fisierul input.txt:
        9
        0,0,2,2,4,1,0,0,8

        in care:
           n=9 - numarul de varfuri
           linia urmatoare contine lista numarului decendentilor asociat fie-
           carui varf in parte

        Un arbore generat este:





        Iesire:  -fisierul output.txt:
        9  5  7
              3  1
                 2
           4
              6  8


                Problema 3
                               Codul buclucas

    Se considera urmatoarea codificare a unui numar natural n dat(n<=15000).
Se porneste de la numarul 1 si se aplica succesiv operatia de incrementare
sau operatia de dublare a rezultatului anterior obtinut(pentru prima operatia
rezultatul anterior considerandu-se numarul 1).
Operatia de incrementare se realizeaza adunand la valoarea curenta orice
numar mai mic strict decat numarul acesta, iar cea de dublare se realizeaza
inmultind cu 2 valoarea curenta.
Incrementarea cu valoarea x se noteaza Ix, iar dublarea valorii y se noteaza
cu Dy.

Exemplu: Pentru a obtine rezultatul 14 putem realiza secventa:

1
1*2=2   cod D1
2+1=3   cod I1
3*2=6   cod D3
6+1=7   cod I1
7*2=14  cod D7
Deci 14 se codifica prin sirul D1I1D3I1D7(fara spatii) de lungime 10.

Cerinte : realizati un program care citeste din fisierul cod.in numarul n si
scrie in fiserul cod.out pe prima linia lungimea codificarii minime a lui n
iar pe a doua linie aceasta codificare minimala.

Exemplu:
        cod.in          cod.out
        14              8
                        D1D2D4I6

Observatie: Poate exista si o alta codificare de lungime minima, dar se va
tipari doar o codificare.

Timp de executie per test : 10 secunde.

                Clasa XI_a
                Problema 1
                 Avansare

Patronul unei firme din motive intemeiate face restructurari si concediaza
un angajat.
El vrea sa multumeasca cat mai multi angajati promovandu-i in functie.
Functiile sunt ierarhizate si promovarea se face in functia imediat ierarhica
sau in urmatoarea acesteia(pe un nivel sau doua superioare)
Se stie ca promovarea in functie inseamna si marirea salariului angajatului
promovat.
Cerinta:
Sa se precizeze care angajat va fi concediat astfel incat sa fie avansati
cat mai multi angajati iar suma majorarilor de salariu a celor avansati sa
nu depaseasca salariu celui concediat.

Date de intrare:
n numar de angajati (n<=100)
m numar de functii  (m<=100)
S vector cu salariile pe fiecare functie
A matricea incadrarii
A[i,j]= 1 daca angajatul i este incadrat in functia j
    0 altfel
Functiile se considera ierarhizate crescator 1......m

Date de intrare se citesc din fisierul FUNCTII.TXT
n m prima linie
S[1] S[2].....S[m]
A[1,1] A[1,2]....A[1,m]
.
.
.
A[n,1] A[n,2]....A[n,m]
Datele pe fiecare linie sunt despartite printr-un unic spatiu.

Datele de iesire se obtin in fisierul AVANSATI.TXT
Pe prima linie numerele j S[j] reprezentand numarul angajatului concediat si
salariul sau.
Pe urmatoarea linie numarul de ordine al angajatilor avansati
i1 i2 ....ip j cu semnificatia i1 ia locul lui i2 ...ip ia locul lui j
Pe linia a treia numarul SS reprezentand suma diferentelor de salariu
ale angajatilor avansati.

Observatie:
1) Patronul va urmari sa aibe in primul rand cat mai multi avansati

2) In cazul in care exista mai multe solutii se va afisa una singura.

Exemplu:
FUNCTII.TXT
3 5
2 3 0 8 0
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
AVANSATI.TXT
2 8
1 3 2
6

Timp de executie per test 1 minut

                PROBLEMA 2


                  Repartizare


    La olimpiada judeteana de informatica participa n licee fiecare
cu un numar de a(i),i:=1..n elevi.Se doreste asezarea elevilor in banci
astfel incit sa nu existe doi elevi de la un liceu in banci consecutive,
iar elevii de la un acelasi liceu sa pastreze ordinea alfabetica.
Ajutati profesorii sa determine o asemenea asezare.
Liceele vor fi codificate de la 1 la n.

Observatie:
    n<=100 si m<=1000;
    Daca exista mai multe solutii se va determina una singura.

Datele se vor citi din fisierul input.txt cu urmatoarea structura:
-pe prima linie doua numere n m (despartite printr-un spatiu) reprezentand
numarul de licee si respectiv numarul total de elevi din concurs.
-pe fiecare din urmatoarele m linii ,departite de un spatiu:
  -numele elevului(fara prenume).
  -codul liceului.

Datele de iesire se vor scrie in fisierul output.txt sub forma urmatoare:
Pe m linii se vor scrie in ordine:
nume cod_liceu separate printr-un spatiu.
In cazul in care asezarea nu este posibila se va scrie in fisier
pe o singura linie mesajul
        Nu exista solutie

Exemplu:
Pentru fisierul de intrare input.txt

3 6
Albu 2
Cezar 2
Manu 3
Duca 1
Ion 2
Popescu 1

Fisierul de iesire output.txt va contine:
Albu 2
Duca 1
Cezar 2
Manu 3
Ion 2
Popescu 1
Timp de executie per test: 3 secunde

                Problema 3.
         Se considera un limbaj rezultat prin folosirea a 4 tipuri de sub-
expresii posibile.Cele 4 tipuri de subexpresii din limbaj se codifica cu li-
terele A,B,S,F,iar regulile de formare a lor sunt:
       1.S=>aSc
       2.S=>bAB
       3.S=>cFwBSSe
       4.S=>g
       5.B=>gB
       6.B=>h
       7.A=>dA
       8.A=>m
       9.A=>nFrBtS
       10.F=>pAB
       11.F=>qFsSiAA
       cu seminificatia:
       'S se poate scrie sub forma cF',adica c,urmat de o alta subexpresie
de tip F.
   Se stie ca o expresie corecta din limbaj incepe intotdeauna prin rezol-
varea tipului de subexpresie S,iar dezvoltarea se face prin transcrierea
primului tip de subexpresie ce apare in cuvantul rezultat,de la stanga la
dreapta.
        Exemplu:
         1    2      7       8       5        5         6
        S=>aSc=>abABc=>abdABc=>abdmBc=>abdmgBc=>abdmggBc=>abdmgghc
        Rezulta:cuvantul 'abdmgghc' face parte din limbaj.
             i.Sa se scrie un program encodor de mesaje,care primeste la
        intrare un mesaj sursa sub forma de secventa numerica si genereaza
        la iesire,daca secventa este corecta,cuvantul din limbaj rezultat
        prin aplicarea regulilor conform numerotarii din secventa.
             Exemplu:
             mesaj sursa:'1,2,7,8,5,5,6' => mesaj codat:'abdmgghc'
             ii.Sa se scrie un program decodor de mesaje din limbajul L,care
        are la intrare un mesaj codat,il verifica daca face parte din
        limbajul L si genereaza in acest ultim caz la iesire decodificarea
        mesajului care consta in sirul regulilor aplicate.
             Exemplu:
             mesaj codat:'abdmgghc' => mesaj decodat:'1,2,7,8,5,5,6'

                               Clasa a XII-a
                Problema 1


 Se considera o matrice  patratica a, de dimensiune n (n<100) cu elemente
numere intregi. Sa se determine o alta matrice b de aceleasi dimensiuni de
intregi cu propietatea ca oricare i,j a(i,j) este egala cu suma elmentelor
din matricea b aflate pe pozitii (k,l)  cu distanta Manhattan de cel mult 1
fata de pozitia (i,j).
Obs : Distanta Manhattan dintre punctele (i,j) si (k,l) se defineste
      ca d=|i-k|+|j-l|.

Intrare:
Fisierul input.txt cu urmatoarea structura :
-pe prima linie n reprezentind dimensiunea matricii
-urmatoarele n linii din fisier contin liniile matricii a
Iesire:
Fisierul output.txt cu urmatoarea structura:
-liniile fisierului contin liniile  matricii b
Ex1:
input.txt
4
6 8 13 9
0 9 10 14
1 1 18 13
-2 9 12 15

output.txt
1 2 4 5
3 1 2 0
-5 1 3 7
2 1 5 3

                    Problema 2
                    Puncte de articulatie

    Se da un graf neorientat conex. Sa se determine punctele de articulatie
ale sale.
    Intrarea se face din fisierul puncte.in care are urmatoarea structura:
    - pe prima linie n<=10000 // reprezentand numarul de noduri
    - fiecare din urmatoarele n linii contine:
        - ni // numarul de muchii incidente cu nodul i
        - in continuare ni numere reprezentand nodurile adiacente
            nodului i.
    Iesirea se va face in fisierul puncte.out ce va contine pe o singura
linie punctele de articulatie in ordine lexicografica.

    Timp de executie per test: 5 secunde.

Exemplu :
  puncte.in     puncte.out
  5         3 4
  2 2 3
  2 1 3
  3 1 2 4
  2 3 5
  1 4


                                Problema 3

                           Dreapta separatoare

Se considera in plan doua multimi de puncte M1 si M2.
Punctele celor doua multimi sunt date prin coordonatele lor, numere intregi.
Cerinta:
Sa se determine o drepta in plan care separa cele doua multimi.

Datele de intrare se citesc din fisierul dr.in astfel:
- pe prima linie numerele n1 n2 reprezentand numarul de puncte al multimii
M1 respectiv M2
- pe urmatoarele n1 linii perechi de numere intregi
despartite prin spatiu reprezentand coordonatele unui punct din multimea M1
Pe urmatoarele n2 linii perechi de numere intregi
despartite prin spatiu reprezentand coordonatele unui punct din multimea M2
In fisier perechile de doua numere sunt despartite printr-un spatiu.
Observatie:
Numerele n1 si n2 sunt mai mici decat 1000.

Ecuatia dreptei determinate va fi afisata pe ecran sub forma
ax+by+c=0 unde a, b, c se vor scrie cu doua zecimale.
In cazul in care nu exista o astfel de dreapta se va afisa pe ecran mesajul:
Nu exista solutie

Exemplu
dr.in
3 2
5 6
10 6
7 4
7 2
10 1
Pe ecran se va afisa:
0.00x+1.00y=3.00























