Realitatea TV



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:
  • inițializare;
  • determinarea numărului de elemente ale șirului;
  • determinarea numărului maxim de comparări pe care le aveți la dispoziție;
  • compararea a două elemente ale șirului a;
  • furnizarea ca rezultat a unui element al permutării p.
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ă:
  • valoarea i nu reprezintă un număr întreg cuprins între 1 și N;
  • valoarea pi nu reprezintă un număr întreg cuprins între 1 și N;
  • valoarea celui de-al i-lea element al permutării p este furnizată a doua oara;
  • valoarea corectă a celui de-al i-lea element al permutării p nu este pi;
  • au fost furnizate valorile tuturor celor N elemente ale permutării (Acesta este singurul caz în care sunt acordate puncte!).
    Toate funcțiile și procedurile (excepție: Init) întrerup execuția programului dacă sunt apelate înaintea inițializării.

    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)			-