Rezolvare completă PbInfo #1439 Sir6

Se dă un şir de N numere naturale. Din acest şir, putem forma un şir comprimat de forma: a[1], b[1], a[2], b[2], …, a[x], b[x], din care înţelegem că numărul a[1] apare pe primele b[1] poziţii, a[2] apare pe următoarele b[2] poziţii…, iar a[x] apare pe ultimele b[x] poziţii.

De exemplu, dacă şirul dat este 1 1 5 5 5 2, atunci şirul comprimat va fi 1 2 5 3 2 1.

Cerința

Să se determine:

a) Lungimea celei mai lungi secvenţe formată din numere egale.
b) Şirul comprimat pentru şirul dat.

Date de intrare

Fișierul de intrare sir6.in conține pe prima linie numerele P şi N. Pe următoarea linie se găseşte un şir format din N numere naturale.

Date de ieșire

Fișierul de ieșire sir6.out va conține pe prima linie:
a) Dacă P este 1, lungimea celei mai lungi secvenţe, reprezentând răspunsul la cerinţa a).
b) Dacă P este 2, şirul comprimat, reprezentând răspunsul la cerinţa b).

Restricții și precizări

  • N <= 100.000
  • Numerele din şir nu depăşesc 1.000.000.
  • P este 1 sau 2.

Exemplul 1

sir6.in

1 6
1 1 5 5 5 2

sir6.out

3

Explicație

Pentru acest test P = 1, deci se va rezolva doar cerinţa a). Secvenţa cea mai lungă formată din numere egale este: 5 5 5 şi are lungimea 3.

Exemplul 2

sir6.in

2 6
1 1 5 5 5 2

sir6.out

1 2 5 3 2 1

Explicație

Pentru acest test P = 2, deci se va rezolva doar cerinţa b). Numărul 1 apare de 2 ori, numărul 5 apare de 3 ori, iar numărul 2 apare o singură dată. Prin urmare, şirul comprimat este 1 2 5 3 2 1.

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 Sir6:

/*
    Author: Rusu Daniel
    Complexity: O(N)
    Verdict: 100/100
*/

#include <fstream>

using namespace std;

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

int P, N, x, mx;

int main() {
    fin >> P >> N;

    int prec = -1;
    int app = 0;

    for(int i = 1; i <= N; ++i) {
        fin >> x;

        if(x != prec) {
            if(P == 2 && prec >= 0) {
                fout << prec << ' ' << app << ' ';
            }
            else {
                mx = max(mx, app);
            }

            prec = x;
            app = 1;
        }
        else {
            ++app;
        }
    }

    mx = max(mx, app);

    if(P == 1) {
        fout << mx;
    }
    else {
        fout << prec << ' ' << app;
    }

    fout << '\n';

    fin.close();
    fout.close();

    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 #1439 Sir6

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1439 Sir6 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!