Se consideră un șir a cu N elemente ale căror valori sunt numere întregi disticte care nu sunt cunoscute.
Va trebui să determinați o permutare p a mulțimii {1, 2, ..., N} astfel încât șirul b ale cărui elemente sunt date de formula b[i] = a[p[i]] (i = 1, ..., N) să fie sortat în ordine crescătoare. Pentru determinarea permutării p puteți efectua un numar limitat de comparări între două elementele ale șirului a. Pentru aceasta aveți la dispoziție o bibliotecă externa care vă pune la dispoziție rutine pentru:
Pentru a putea folosi biblioteca va trebui să includeți în programul dumneavoastră istrucțiunea uses sort; pentru limbajul Pascal și #include "sort.h" pentru limbajul C/C++. În continuare sunt prezentate sintaxele funcțiilor și procedurilor incluse în biblioteci:
procedure Init; void Init() - trebuie apelată la începutul programului și este folosită de către bibliotecă pentru inițializare; - întrerupe execuția programului dacă este apelată a doua oară. function GetN:Integer; int GetN() - returnează numărul de elemente (N) ale șirului a (și ale permutării p care trebuie determinată). function GetNoComp:Integer; int GetNoComp() - returnează numărul de comparări (apeluri ale funcției IsGreater) pe care le mai aveți la dispoziție (în momentul apelului funcției GetNoComp) pentru determinarea permutării p. function IsGreater(i,j:Integer):Boolean; int IsGreater(int i,int j) - returnează true (valoare nenulă) dacă a[i] > a[j] și false (0) în caz contrar; - întrerupe execuția programului dacă cel puțin una dintre valorile i și j nu nu este un număr întreg cuprins între 1 și N sau dacă numărul de apeluri ale acestei funcții depășește numărul maxim permis. function Result(i,pi:Integer):Boolean; int Result(int i, int pi) - acceptă ca rezultat faptul că al i-lea element al permutării p este pi; - întrerupe execuția programului dacă:
Programul vostru nu va citi datele din nici un fișier de intrare și nu va scrie date în nici un fișier de ieșire.
2 <= N <= 255.
Subprogram apelat Valoare returnată
Init - GetN 5 GetNoComp 8 IsGreater(1,2) false (0) IsGreater(3,4) false (0) IsGreater(4,5) false (0) IsGreater(3,5) false (0) IsGreater(1,3) false (0) IsGreater(2,3) true (1) IsGreater(2,4) true (1) IsGreater(2,5) false (0) Result(1,1) - Result(2,3) - Result(3,4) - Result(4,2) - Result(5,5) - |