Subiectul al III-lea, 3. b)

3. O pereche de numere naturale (x,y) se numește p-ordonată dacă x și y au paritate diferită, cu x>y, sau dacă x și y au aceeași paritate. Exemplu: (7,4), (8,7), (7,9) sunt perechi p-ordonate, dar (7,8), (8,9) nu sunt perechi p-ordonate.

Un șir, format din 2·n numere naturale, se numește p-ordonat dacă perechile de forma (x,y) sunt p-ordonate, pentru orice x, dintre primii n termeni ai șirului, și orice y, dintre ultimii n termeni ai șirului. Fișierul bac.txt conține numere naturale din intervalul [0,10⁶]: pe prima linie un număr nenul, n, iar pe a doua linie un șir de 2·n numere, separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA, în cazul în care șirul aflat în fișier este p-ordonat, sau mesajul NU, în caz contrar. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate. Exemplu: dacă fișierul are unul dintre conținuturile de mai jos, se afișează pe ecran mesajul DA.

5 22 37 21 8 15 2 3 14 4 5

5 22 36 20 8 14 44 42 4 2 5

Identificatorii utilizați în rezolvări trebuie să respecte precizările din enunț (bold), iar în lipsa unor precizări explicite, notațiile trebuie să corespundă cu semnificațiile asociate acestora (eventual în formă prescurtată). Datele de intrare se consideră corecte, validarea lor nefiind necesară.