Un șir format din 2·n numere naturale se numește paritar dacă fiecare dintre primii săi n termeni fie
are aceeași paritate cu oricare dintre ultimii săi n termeni, fie este strict mai mic decât oricare număr
de paritate diferită aflat printre aceștia.
Fișierul bac.txt conține numere naturale din intervalul [0,106]: 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 paritar, 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
20 3 11 4 15 25 49 18 53 16
5
20 3 11 4 15 25 49 81 53 61
a) Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
b) Scrieți programul C/C++ corespunzător algoritmului proiectat. (8p.)
Răspunsuri la întrebare
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("bac.txt");
int n, i, num,p1,i1,p2,i2,maxp1,maxi1,minp2,mini2, paritar;
int main()
{
f >> n;
for (i=1; i<=n; ++i)
{
f >> num;
if (num%2)
{
if (i1==0) {maxi1=num; i1=1;}
else if (num>maxi1) maxi1=num;
}
else
{
if (p1==0) {maxp1=num; p1=1;}
else if (num>maxp1) maxp1=num;
}
}
for (i=n+1; i<=2*n; ++i)
{
f >> num;
if (num%2)
{
if (i2==0) {mini2=num; i2=1;}
else if (num<mini2) mini2=num;
}
else
{
if (p2==0) {minp2=num; p2=1;}
else if (num<minp2) minp2=num;
}
}
if (p1*i1)
{
if (p2*i2) paritar=1;
else
{
if (p2)
{
if (maxi1<minp2) paritar=1;
}
else
{
if (maxp1<mini2) paritar=1;
}
}
}
else
{
if (p1)
{
if (p2) paritar=1;
else
{
if (maxp1<mini2) paritar=1;
}
}
else
{
if (i2) paritar=1;
else
{
if (maxi1<minp2) paritar=1;
}
}
}
if (paritar) cout << "DA";
else cout << "NU";
}