Subiectul al III-lea, 3. a)

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