Comparari
Fie un sir de N numere întregi. Numim al doilea maxim al sirului cel mai mare numar din sir, cu exceptia maximului. Pentru a afla maximul si al doilea maxim, veti efectua comparari între elementele sirului.
Având la dispozitie numai N+[log2 N]
-2 comparari, aflati pozitiile pe care le ocupa maximul si al doilea maxim. Prin [log2 N] s-a notat partea întreaga superioara a lui „logaritm în baza 2 din N".
Cerinta
Aflati cele doua numere, efectuând cel mult N+[log2N]
-2 comparari. Pentru a putea efectua compararile, comisia va pune la dispozitie functia:(pentru cei care programeaza în C sau C++),
respectiv functia
care compara numarul de pe pozitia
i cu cel de pe pozitia j si va returneaza 1, daca elementul aflat pe pozitia i este mai mare sau egal cu cel de pe pozitia j, respectiv -1, în caz contrar.Programul trebuie sa apeleze la început functia
GetN care returneaza numarul de elemente din sir. Apelul va fi de forma N=GetN(), pentru programatorii în C (si C++), respectiv N:=GetN, pentru programatorii în Pascal, unde am presupus ca N este variabila de tip int, respectiv Integer, în care este memorata lungimea sirului. Este esential ca apelul functiei GetN sa preceada apelurile functiei Compara si în plus, sa existe un singur apel al functiei GetN (în caz contrar programul va primi 0 puncte pe acel test). Mai jos aveti doua link-uri catre fisierele ce reprezinta sursele unit-ului comisiei:În fisierul
Compar.out veti scrie pozitiile pe care se afla maximul sirului si al doilea maxim, separate printr-un blanc.Pentru a folosi unitul, trebuie sa creati fisierul
Compar.in, în care veti scrie pe prima linie numarul N, iar pe a doua linie elementele sirului, separate prin câte un spatiu.Restrictii
Exemplul 1
Daca sirul considerat este (5, 3, 4), atunci o executare corecta a programului este urmatoarea:
…;
N = GetN()
, obtineti N=3;Compara (1, 2)
, se returneaza 1;Compara (1, 3)
, se returneaza 1;Compara (2, 3)
, se returneaza –1;În acest moment ati epuizat numarul de comparari permise (
3+2-2=3 comparari) si în fisierul Compar.out veti scrie numerele 1 si 3, separate printr-un spatiu, reprezentând pozitiile pe care se afla maximul sirului (5), respectiv al doilea maxim (4).Exemplul 2
Daca sirul considerat este (
5, 7, 7), o executare corecta a programului este urmatoarea:…;
N = GetN()
, obtineti N =3;Compara (1, 2)
, se returneaza -1;Compara (2, 3)
, returneaza 1;Compara (1, 3)
, se returneaza –1;…;
În acest moment ati epuizat numarul de comparari permise (
3+2-2=3 comparari) si în fisierul Compar.out veti scrie numerele 2 si 3, separate printr-un spatiu, reprezentând pozitiile pe care se afla maximul sirului (7), respectiv al doilea maxim (7).Observatie:
Pentru acest exemplu, mai exista o solutie corecta, cea în care considerati maximul (7) pe pozitia 3 si al doilea maxim (7) pe pozitia 2.
Timp maxim de executare/test: 1 secunda.
Se garanteaza ca 1008 apeluri ale functiei Compara, împreuna cu un apel al functiei GetN nu dureaza mai mult de 0.1 secunde.
În timpul concursului, pentru a va putea testa programele, veti avea la dispozitie module echivalente cu cele pe care le va utiliza comisia în timpul evaluarii programelor voastre.