
	1. Se da un graf neorientat cu N virfuri si M muchii. Pentru trei
virfuri A,B,C sa se determine daca exista un ciclu elementar care sa treaca
prin A si B si care sa nu treaca prin C.
Limite:   N<=1.000, M<=10.000
Intrare:
  Fisierul de intrare contine mai multe seturi de date. Un set de
date este format dintr-o linie pe care este scris N A B si C, urmata de
M linii pe care sint date muchiile, cite una pe linie. Muchia (i,j) este
data sub forma:
i j
Fiecare set se termina cu o linie goala.
Iesire:
 Pentru fiecare set de date se va scrie o linie continind
1
in cazul in care exista ciclu si respectiv
0
in caz contrar.

Exemplu:
//intrare:
4 2 1 4         // N A B C
1 2             // muchia {1,2}
2 3             // muchia {2,3}
3 4             //...
4 1
3 1
4 2 1 4         // N A B C - al doilea set
1 2             // muchia {1,2}
2 3             // muchia {2,3}
3 4             //...
4 1

//iesire:
1              // exista ciclu
0              // nu exista ciclu

========================================================

	2. Sunteti angajat la o companie care asigura servicii de transport marfuri en 
gross. Clientii au magazine in orase din toata tara si ei sunt aprovizionati 
din depozite locale ale companiei. Pentru o aprovizionare optima, compania vrea
sa investeasca in construirea unui depozit central din care sa se aprovizioneze
toate zonele; va fi deci necesar ca acest depozit sa fie plasat intr-unul din
orase in asa fel incat timpul total de livrare din acest depozit in toate 
orasele sa fie minim. Camioanele companiei transporta marfa la depozitele 
locale si se intorc la depozitul central. Timpul de livrare este format din 
timpul necesar parcurgerii drumului de la depozitul central la oras si inapoi 
(se presupune ca soferul va urma de fiecare data calea cea mai rapida, iar in 
fiecare oras depozitul local este chiar la intrare) si timpul de descarcare al
camionului la destinatie, care este de exact 30 minute. Drumurile care leaga 
orasele sunt de aceeasi calitate, dar pot exista drumuri care iau mai mult timp 
intr-un sens decat in sens invers. Pot fi de exemplu drumuri cu sens unic. 
Pentru a simplifica modelul, s-a stabilit pentru fiecare oras o lista cu toate 
drumurile care pleaca din oras spre celelalte orase si cat timp ia parcurgera 
fiecarui drum.

Intrare:
	Datele sunt intr-un fisier text al carui nume se citeste la tastatura,
si contine date pentru mai multe situatii. Fiecare situatie incepe cu o linie 
pe care se afla un numar intreg n (2<=n<=50) care reprezinta numarul de orase. 
Urmeaza n linii pentru cele n orase. Pe fiecare linie se afla intai numarul p 
de drumuri care pleaca din oras, urmat de p perechi de numere care contin 
numarul orasului de destinatie al drumului respectiv timpul necesar pentru 
parcurgerea lui (in minute). Orasele sunt numerotate cu numere de la 1 la n.
Numarul de minute pentru a parcurge orice segment de drum este in intervalul
[10,120]. Orice doua orase sunt legate direct prin cel mult un drum si din 
orice oras pleaca cel putin un drum.
Fisierul de intrare se termina cu o situatie descrisa de 0 orase.

Iesire:
Pentru fiecare situatie trebuie scoasa pe ecran o linie continand numarul 
orasului de la care livrarea totala este optima si ce timp de livrare ii 
corespunde.
Daca sunt mai multe orase in care este atins minimul, ele trebuesc listate in
ordinea crescatoare a numerelor, cu timpul de livrare la sfarsit.
Toate numerele se separa prin cate un spatiu.

Exemplu:
Intrare:
5
2 2 70 4 55
3 1 70 3 30 5 65
3 2 30 5 40 4 35
3 1 55 3 35 5 50
3 2 65 3 40 4 50
2
1 2 35
1 1 25
0
Iesire:
3 540
1 2 120
=================================

	3. Matematicienilor le place sa lucreze cu diverse proprietati ale numerelor.
De exemplu, ei considera 945 ca un numar interesant deoarece acesta este 
cel mai mic numar impar in care suma divizorilor numarului este mai mare decat
numarul insusi.
	Pentru a-i ajuta sa caute numere interesante, scrieti un program care 
parcurge un interval de numere si determina cate din acestea au cel mai mare
numar de divizori. Din pacate marimea numerelor si marimea intervalului sunt
asa de mari incat o simpla baleiere ia mult timp. Asa ca fiti siguri ca 
algoritmul vostru este suficient de eficient pentru a acoperi cel mai mare
interval posibil in cateva secunde.
Intrare:
Prima linie a intrarii da numarul N de intervale; fiecare din urmatoarele N 
linii contine cate un interval format dintr-o limita inferioara L si o limita
superioara U (1<=L<=U<=1.000.000.000, 0<=U-L<=10.000).
Se considera intervalele inchise.
Iesire:
Pentru fiecare interval se afla numarul P care are cei mai multi divizori (daca
sunt mai multe astfel de numere, se selecteaza cel mai mic) si numarul D al
divizorilor pozitivi ai lui P (inclusiv P). Se va tipari textul:
"Intre L si U, P are un maxim de D divizori", unde L,U,P si D sunt numerele 
definite mai sus.
Exemplu: Pentru intrarea:
3
1 10
1000 1000
999999900 1000000000
	iesirea va fi
Intre 1 si 10, 6 are un maxim de 4 divizori
Intre 1000 si 1000, 1000 are un maxim de 16 divizori
Intre 999999900 si 1000000000, 999999924 are un maxim de 192 divizori
==================================================

	4. Sa observam pe cineva care joaca Mastermind. Scopul acestui joc este 
de a afla un cod secret, combinand rationamentul logic cu ghicitul.
In cazul de fata, codul secret este un numar de 4 cifre aflat intre 0000 si
9999; sa spunem de exemplu 3321. Jucatorul incepe cu un numar ales la 
intamplare, sa spunem 1223; pentru fiecare din urmatoarele incercari, primeste 
un raspuns din care reiese cat de aproape este de numarul corect. Raspunsul 
consta din doua numere: numarul cifrelor corect ghicite (in acest caz, una: 
2 pe a treia pozitie) si numarul cifrelor ghicite corect dar gresit asezate 
(in acest caz, doua: 1 si 3). Calculatorul va afisa deci 1/2.
Scrieti un program care, plecand de la un set de numere date si raspunsurile 
corespunzatoare, va afla codul corect.
Intrare:
Pe prima linie a fisierului de intrare este numarul N al testelor pe care le
va trece programul tau. Fiecare test consta dintr-o prima linie continand 
numarul de ghiciri G (0<=G<=10), urmata de 10 linii, fiecare din 8 caractere: 
un cod de 4 cifre, un spatiu, o cifra indicand numarul de cifre corect ghicite, 
un slash (/), si in final, o cifra indicand numarul cifrelor ghicite corect dar 
nepozitionate corect.
Iesire:
Pentru fiecare test, iesirea va consta dintr-o linie continand unul din 
raspunsurile:
imposibil - daca nu exista nici un cod consistent cu intrarea;
codul secret - daca exista un singur cod consisitent cu datele de intrare;
nedeterminat - daca datele de intrare sunt verificate de mai multe coduri 
		posibile.
Exemplu: Pentru intrarea:
4
6
9733 0/1
2384 0/2
6264 0/1
3383 1/0
2795 0/0
0218 1/0
1
1234 4/0
1
1234 2/2
2
6428 3/0
1357 3/0
   iesirea va fi:
3411
1234
nedeterminat
imposibil
=============================================
 
	5. Problem H {Numarand Patern-uri}. Fie doua nuumere n,k (n>0,k>0)
O configuratie a unei n-k-forme este un vector cu n elemente alese din domeniul
[-k..k], a caror suma este zero. Doua configuratii sunt echivalente daca se pot
obtine una din alta prin: (a) permutari ciclice cu una sau mai multe pozitii,
(b) scrierea inversa a configuratiei, (c) schimbarea semnului tuturor numerelor,
(d) combinatii intre (a),(b) si (c). O clasa de echivalenta de configuratii este
numita un n-k-patern.
	De exemplu, (0,1,1,-2) este o configuratie pentru o 4-2-forma. Alte
configura]ii echivalente sunt: 
(a) (1,-2,0,1), (b) (-2,1,1,0), (c) (0,-1,-1,2) si (d) (-1,-1,0,2).
Sunt 14  4-2-patern-uri posibile, reprezentate lexicografic astfel:
(0,0,0,0)    (2,-2,2,-2)  (2,0,0,-2)   (1,-1,1,-1)  (2,-1,0,-1)  (2,1,-2,-1)
(1,0,-1,0)   (2,-1,1,-2)  (2,1,-1,-2)  (1,0,0,-1)   (2,0,-2,0)   (2,2,-2,-2)
(1,1,-1,-1)  (2,0,-1,-1)
  Se cere un program care sa calculeze numarul de paternuri pentru o secventa 
de n-k-forme.
Intrare:
   Fisierul de intrare este o secventa de perechi de intregi n,k separate
prin un singur spatiu. fiecare pereche apare pe o singura linie. Fisierul de
intrare se termina cu end-of-file. Valoarea maxima pentru n+k este 11.
Iesire:
   Fisierul de iesire contine o secventa de numere intregi, cate unul pe linie.
 Fiecare numar reprezinta numarul de paternuri pentru n-k-formele de la intrare.
Exemplu: Pentru intrarea:
8 0
4 2
   la iesire va apare:
1
14
=======================================

	6. Departamentul central de pompieri colaboraza cu departamentul de 
transporturi pentru actualizarea hartii retelei de drumuri. In fiecare zi
mai multe strazi sunt inchise pentru reparatii sau constructii. Pompierii
trebuie sa le cunoasca pentru a putea sa selecteze strazile accesibile de 
la statia lor la incendiu.
	Orasul este impartit in mai multe districte de pompieri care nu se
intersecteaza intre ele; fiecare district este deservit de o singura statie
de pompieri. Cand se anunta un incendiu, un dispecerat central alerteaza 
statia din districtul unde este acest incendiu si da o lista de drumuri 
posibile de la statie la foc.
	Trebuie sa scriti un program care sa poata fi folosit de dispeceratul 
central pentru a genera toate traseele posibile de la statii la incendiu.
Intrare si Iesire:
	Orasul dispune de cate o harta separata pentru fiecare district de
pompieri. Capatele strazilor din fiecare harta sunt identificate prin numere
intregi pozitive mai mici decat 21, cu statia de pompieri in capatul numarul 1.
fisierul de intrare contine mai multe teste reprezentand incendii in diverse 
districte. Pe prima linie a unui test se afla un singur intreg care este
numarul capatului de strada cel mai apropiat de incendiu.
	Urmatoarele linii constau din perechi de numere intregi pozitive 
separate prin cate un spatiu, fiecare reprezentand cele doua capate ale unie
strazi pe care se poate circula. (De exemplu, daca pe o linie se afla perechea
4 7, atunci strada dintre capatele 4 si 7 este deschisa si intre 4 si 7 nu
mai sunt alte capete de strazi.). Linia finala din fisierul de intrare este
0 0
Pentru fiecare test de intrare, iesirea va trebui sa identifice numarul cazului
(caz #1, caz #2, etc.). Pe fiecare linie trebuie listat un drum, cu capatele 
strazilor scrise in ordinea in care apar pe drum, fiecare capat de drum fiind
in lista cel mult odata (evident pompierii nu vor sa se invartesca in cerc).
Trebuiesc listate toate drumurile posibile de la statia de pompieri a 
districtului pana la incendiu. Pe ultma linie se afiseaza numarul total de 
drumuri posibile, ca in exemplu.
Exemplu:
Intrare:
6
1 2
1 3
3 4
3 5
4 6
5 6
2 3
2 4
0 0
4
2 3
3 4
5 1
1 6
7 8
8 9
2 5
5 7
3 1
1 8
4 6
6 9
0 0
Iesire:
Caz 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
Sunt 7 drumuri de la statie la capatul de strada 6.
Caz 2:
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
Sunt 8 drumuri de la statie la capatul de strada 4.
============================================

	7. Jocul se joaca in doi. Initial, pe cmpul de joc se afla mai
multe gramezi de pietre. Alternativ, fiecare juc[tor isi alege o gramada 
formata din cel putin doua pietre si o imparte in doua gramezi mai mici. 
Miscarile se fac pe rnd, pna cnd toate gramezile contin cte o singura 
piatra. Cstiga jucatorul care face ultima miscare. Trebuie sa scrieti un 
program care, pentru o configuratie initiala data, determina daca jucatorul 
care face prima mutare are strategie de cstig.
Fisierul de intrare contine pe fiecare linie cte o configuratie initiala (sub 
forma unui sir de numere). Pentru fiecare configuratie trebuie sa afisati o 
linie cu mesajul "Primul jucator are strategie de cstig" daca acest lucru este
adevarat si "Primul jucator nu are strategie de cstig" in caz contrar.
-------------------------------------

 	8. Sa consideram un examen la istorie in care li se cere studentilor sa aseze
mai multe evenimente istorice in ordine cronologica. Cei are ordoneaza corect 
toate evenimentele vor primi nota maxima, dar cum vor fi notati cei care 
aranjeaza gresit unul sau multe evenimente ?
Pot fi luate in considerare mai multe posibilitati:
1. Sa se acorde un punct pentru fiecare eveniment a carui pozitie este corecta;
2. Sa se acorde un punct pentru fiecare eveniment in cea mai lunga (nu neaparat
consecutiva) secventa de evenimente care sunt asezate corect unele in raport cu
altele.
De exemplu, daca patru evenimente apar in ordinea 1 2 3 4, atunci ordinea
1 3 2 4 va primi doua puncte cu prima metoda (evenimentele 1 si 4 sunt pe 
pozitii corecte) si trei puncte cu a doua metoda (secventele de evenimente 
1 2 4 si 1 3 4 sunt asezate cronologic corect).
Vom avea nevoie de un program care sa acorde numarul de puncte la examen pentru
a doua metoda de notare.
Problema:
   Fiind date n evenimente 1,2,..,n asezate cronologic in ordinea c1,c2,..,cn
(1<=ci<=n), si o secventa de raspunsuri ale unui student r1,r2,..,rn (1<=ri<=n)
sa se determine lungimea celei mai lungi secvente (nu neaparat consecutive) de
evenimente asezate in ordine cronologica corecta de catre student.
Intrare:
Prima linie a fisierului de intrare (nume dat la tastatura) este un numar intreg
n care reprezeinta numarul de evenimnete. A doua linie contine n numere intregi
indicand cele n evenimente in ordine cronologica.
Pe fiecare din liniile urmatoare se va afla raspunsul unui student: n numere 
intregi distincte reprezentand ordinea cronologica a evenimentelor, presupusa 
de acesta. Doua numere de pe o linie sunt separate prin cel putin un spatiu.    
Iesirea:
Pentru fiecare ordonare data de un student, se cere afisarea pe ecran a 
punctajului obtinut de acesta. Pentru fiecare student va fi o linie de iesire.
Exemplu:
	 Pentru intrarea:
4
4 2 3 1
1 3 2 4
3 2 1 4
2 3 4 1
iesirea este;
1
2
3
	Pentru intrarea:
10
3 1 2 4 9 5 10 6 8 7
1 2 3 4 5 6 7 8 9 10
4 7 2 3 10 6 9 1 5 8
3 1 2 4 9 5 10 6 8 7
2 10 1 3 8 4 9 5 7 6
iesirea este:
6
4
10
5
=======================================

	9. Sa consideram o tara cu N orase; intre oricare doua orase sunt
stabilite drumuri directe de lungime egala cu 1. Acest sistem rutier
este numit par-impar daca exista doua orase intre care au loc legaturi
prin cel putin doua drumuri: unul de lungime para si altul de lungime impara.
a) Stabiliti daca sistemul de drumuri este de tip par-impar.
b) Daca raspunsul la a) este negativ, determinati o submultime maximala
X de orase care satisface conditia: orice doua orase din X, daca sunt
unite cu un drum, acesta este de lungime para.
  Numele fisierului de intrare este introdus de la tastatura. Prima sa
linie contine valoarea lui N (N<=300); pe urmatoarele linii se afla
perechi I,J cu semnificatia ca orasele I si J sunt legate direct.
  Iesirea va fi realizata pe ecran intr-o forma inteligibila.
  Exemple: Daca fisierul de intrare contine:
5
1 2
2 3
3 4
4 5
5 1
o iesire valida este:
YES
Daca fisierul de intrare contine:
3
1 2
atunci o iesire valida este:
NO
X are 2 elemente
X: 2 3
================================
