Cupa Siveco - concurs national de software educational



Se consideră un șir a cu 2 * N elemente ale căror valori sunt numere întregi distincte, generate aleator, care nu sunt cunoscute. Se știe că atât primele N elemente ale șirului (cele de pe pozițiile 1, 2, ..., N), cât și ultimele N elemente ale acestuia (cele de pe pozițiile N + 1, N + 2, ..., 2 * N) sunt ordonate crescător.
    Va trebui să determinați unul dintre indicii elementelor aflate pe pozițiile N sau N + 1 în șirul obținut prin ordonarea în ordine crescătoare a șirului a. Pentru determinarea acestui indice, puteți efectua un număr limitat de comparări între două elemente ale șirului a și aveți dreptul la două încercări de a "ghici" acest indice.
    Pentru aceasta aveți la dispoziție o bibliotecă externă 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 rezultatului.
Pentru a putea folosi biblioteca va trebui să includeți în programul dumneavoastră instrucțiunea uses middle; pentru limbajul Pascal și #include "middle.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 Get2N:Integer;
int Get2N()

returnează numărul de elemente (2 * N) ale șirului a.

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 rezultatului.

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 este un număr întreg cuprins între 1 și 2 * N sau dacă numărul de apeluri ale acestei funcții depășește numărul maxim permis.

procedure Result(x:Integer);
void Result(int x)

acceptă ca rezultat faptul că elementul de pe poziția x a șirului a se află pe una dintre pozițiile N sau N + 1 în șirul obținut după ordonare;
întrerupe execuția programului dacă valoarea x reprezintă un rezultat corect sau dacă este apelată a doua oară și valoarea x nu reprezintă un rezultat corect.

    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 <= 2457.
atât indicele elementului de pe poziția N, cât și indicele celui de pe poziția N + 1 sunt considerate rezultate corecte.
doar unul dintre apelurile permise ale rutinei Result trebuie să furnizeze un răspuns corect.


Subprogram apelat                        Valoare returnată
Init				-
Get2N				6
GetNoComp			2
IsGreater(2,5)			false (0)
IsGreater(1,4)			false (0)
Result(5)			-
Result(4)			-