Cerinţa

Se dă un şir cu n elemente, numere naturale. Determinaţi cea mai lungă secvenţă de elemente din şir cu proprietatea că oricare două valori consecutive în secvenţă au parităţi diferite.

Dacă există mai multe secvente de lungime maximă cu această proprietate, se va determina aceea cu suma elementelor maximă. Dacă există mai multe secvenţe de lungime maximă cu aceeaşi sumă maximă a elementelor se va determina cea mai din dreapta.

Date de intrare

Fişierul de intrare secventa.in conţine pe prima linie numărul n; urmează cele n elemente ale şirului, dispuse pe mai multe linii şi separate prin spaţii.

Date de ieşire

Fişierul de ieşire secventa.out va conţine pe prima linie două numere p şi u, separate printr-un spaţiu, reprezentând indicele primului, respectiv al ultimului element din secvenţa determinată.

Restricţii şi precizări

1 ≤ n ≤ 100.000;
elementele şirului vor avea cel mult 9 cifre şi sunt numerotate de la 1 la n;

Exemplu

secventa.in

10
2 4 3 6 7 5 2 5 8 10

secventa.out

6 9

Explicație

Există două secvenţe de elemente care respectă regula precizată de lungime maximă. Suma elementelor din cele două secvenţe este aceeaşi, astfel că s-a afişat secvenţa cea mai din dreapta.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Secventa:

#include <iomanip>
#include <fstream>
#include <iostream>
#include <cassert>
using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");


int main(){
    int p, u, n;
    int x[100005], SMax = -1;
    fin >> n;
    for(int i=1 ; i<=n ; i++)
        fin >> x[i];
    p = 1, u = -1;
    SMax = -1;
    for(int i=1 ; i<=n ; i++){
        int j = i+1 , s=x[i];
        while(j<=n && x[j]%2 != x[j-1]%2)
            s += x[j], j++;
        if(j-i> u-p+1)
            u = j-1, p = i, SMax = s;
        else
            if(j-i == u-p+1)
                if(s > SMax)
                    u = j-1, p = i, SMax = s;
                else
                    if(s == SMax)
                        u = j-1, p = i;
        i = j-1;
    }
    fout << p << " " << u;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #283 Secventa

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #283 Secventa de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #283 Secventa