12. ZBIROVI NAKON PODELE - REŠENJE
TEKST ZADATKA: 12. zadataka sa webstrane: Kvalifikacije za okružna takmičenja
Uputstvo:
Zadatak se može rešiti tako što se niz prvo učita, a zatim se u prolazku kroz petlju od posledne ka početnoj poziciji određuje broj neparnih pojavljivanja u nizu desno od te pozicije i zapisuje u pomoćni niz.
Zatim se u još jednom prolasku kroz niz, ovoga puta sa leva na desno određuju broj parnih levo i desno od tekuće pozicije, kao i broj neparnih i levo i desno od tekuće pozicije. Za određivanje broja parnih i neparnih desno se koriste zapisane vrednosti u pomoćnom nizu.
Ukupan broj parova je zbir proizvoda parnih i neparnih vrednosti levo i desno od tekuće pozicije "i". Npr. ako traženu vrednost označimo sa b, a pomoćni niz sa bn, ukupan broj elemenata sa n, onda se b računa:
Zatim se u još jednom prolasku kroz niz, ovoga puta sa leva na desno određuju broj parnih levo i desno od tekuće pozicije, kao i broj neparnih i levo i desno od tekuće pozicije. Za određivanje broja parnih i neparnih desno se koriste zapisane vrednosti u pomoćnom nizu.
Ukupan broj parova je zbir proizvoda parnih i neparnih vrednosti levo i desno od tekuće pozicije "i". Npr. ako traženu vrednost označimo sa b, a pomoćni niz sa bn, ukupan broj elemenata sa n, onda se b računa:
brojNeparnihDesno=bn[i];
brojParnihDesno=n-bn[i];
b= brojParnihLevo*brojParnihDesno + brojNeparnihLevo*brojNeparnihDesno;
Ovo proizilazi iz toga što ako je broj neparan u levom nizu mora se sabrati sa neparnim brojem iz desnog niza da bi se dobio paran zbir i obrnuto, ako je broj paran unutar levog niza, mora se sabrati sa parnim brojem iz desnog dela.
Kada se izračuna b upoređuje se sa trenutnim maksimumom i ako je veći ta vrednost postaje maksimum. Tako će se premeštanjem i-te pozicije koja deli niz, udesno, do kraja, dobiti najveći parni zbir parova.
Rešenje
#include < iostream >
using namespace std;
int main()
{
using namespace std;
int main()
{
int n;
cin >> n;
int a[n];
int bnep[n];
int nep=0;
for(int i = 0;i < n;i++)
{
cin >> a[i];
}
bnep[n-1]=0;//broj neparnih desno od pozicije n-1
for(int i = n-1; i > 0; i--)
{
int nepL=0,b=0,parDesno=0,parLevo=0;
int maxPar=0;
for(int i = 0;i < n;i++){
cout << maxPar << endl;
return 0;
}
cin >> n;
int a[n];
int bnep[n];
int nep=0;
for(int i = 0;i < n;i++)
{
cin >> a[i];
}
bnep[n-1]=0;//broj neparnih desno od pozicije n-1
for(int i = n-1; i > 0; i--)
{
if(a[i] % 2 != 0){
if(i > 0){
}
nep++;
}if(i > 0){
bnep[i-1]=nep;//broj neparnih desno od pozicije i-1
}int nepL=0,b=0,parDesno=0,parLevo=0;
int maxPar=0;
for(int i = 0;i < n;i++){
parDesno=n-(i+1)-bnep[i];//broj parnih sa desne strane
if(a[i] % 2 != 0) //tekuci broj je neparan
{
else //tekuci broj je paran
{
b=(parLevo*parDesno)+(nepL*bnep[i]); //broj parova ako bi niz bio podeljen na trenutnoj poziciji
if(b > maxPar)
{
}if(a[i] % 2 != 0) //tekuci broj je neparan
{
nepL++;
}else //tekuci broj je paran
{
parLevo=i+1-nepL; //broj parnih levo se dobije kad
//od ukupnog broja levo(i+1) oduzme broj neparnih levo
}//od ukupnog broja levo(i+1) oduzme broj neparnih levo
b=(parLevo*parDesno)+(nepL*bnep[i]); //broj parova ako bi niz bio podeljen na trenutnoj poziciji
if(b > maxPar)
{
maxPar=b;
}cout << maxPar << endl;
return 0;