Rezolvare completă PbInfo #1143 Dominant

Considerând un șir de valori binare, numim secvență dominantă un set de elemente aflate pe poziții consecutive în șir care are proprietatea că numărul valorilor egale cu 1 este strict mai mare decât numărul valorilor de 0. De exemplu, în șirul 1,0,0,0,1,1,0,1,1,1,0,0 o secvență dominantă este 0,1,1 și o alta, de lungime mai mare, este 0,1,1,0,1,1,1. Secvența dominantă maximală este secvența dominantă de lungime maximă. În șirul din exemplu secvența dominantă maximală este 1,0,0,0,1,1,0,1,1,1,0 (adică întreg șirul, fără ultimul zero).

Cerinţă

Dat fiind un șir de valori binare, să se determine lungimea unei secvențe dominante maximale precum și numărul acestor secvențe.

Date de intrare

Fișierul de intrare dominant.in conține pe prima linie un număr natural V, iar pe linia a doua șirul de valori binare, fără spații.

Date de ieșire

Fișierul de ieșire dominant.out va conține:

  • varianta 1: dacă V=1, atunci pe prima linie a fișierului de ieșire va fi un singur număr natural reprezentând lungimea unei secvențe dominante maximale.
  • varianta 2: dacă V=2, atunci pe prima linie a fișierului de ieșire va fi un singur număr natural reprezentând numărul secvențelor dominante maximale.

Restricții și precizări

  • V poate fi 1 sau 2
  • Lungimea șirului de valori binare este de cel mult 300 000.
  • Pentru toate testele șirul binar va conține cel puțin o valoare de 1.
  • Pentru 60% din punctaj V = 1.

Exemplul 1

dominant.in

1
100011011100

dominant.out

11

Explicație

Secvența dominantă maximală este 10001101110 și are lungimea 11.

Exemplul 2

dominant.in

2
100011011100

dominant.out

1

Explicație

Secvența dominantă maximală este 10001101110 și are lungimea 11. Este o singură secvență dominantă maximală.

Exemplul 3

dominant.in

1
0000110000111

dominant.out

9

Explicație

Secvența dominantă maximală are lungime 9; aceasta este 110000111.

Exemplul 4

dominant.in

2
10000111000

dominant.out

3

Explicație

Secvența dominantă maximală are lungimea 5. Sunt trei secvențe dominante maximale: 00111, 01110 și 11100.

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

/*
   Complexitate O(n) - 100 puncte
*/
#include <iostream>
#include <fstream>
#include <cstring>
#define Nmax 300005
#define inFile  "dominant.in"
#define outFile "dominant.out"

using namespace std;

char s[Nmax];
int x[2*Nmax], y[2*Nmax], *st, *dr;
int optiune;

int main()
{
    int i, n, suma, vmin, vmax, lgMax;
    /// citire
    ifstream fin(inFile);
    ofstream fout(outFile);
    fin >> optiune;
    fin >> (s + 1);

    s[0] = '*';
    n = strlen(s + 1);

    suma = 0;
    for (i = 1; i <= n; i++)
        if (s[i] == '1') suma++;
        else suma--;
    if (suma > 0) /// intregul sir este dominant
    {
        if (optiune == 1) fout << n << "\n";
        else fout << "1\n";
        fout.close();
        return 0;
    }

    st = x + Nmax;
    dr = y + Nmax;

    /// initializare st si dr
    for (i = -n; i <= n; ++i)
    {
        st[i] = 10000000;
        dr[i] = -10000000;
    }

    /// calcul st si dr
    /// st[i] = cea mai din stanga pozitie unde apare valoarea i
    /// dr[i] = cea mai din dreapta pozitie unde apare valoarea i
    st[0] = dr[0] = 0;
    suma = 0;
    vmin = 10000000;
    vmax = -10000000;
    for (i = 1; s[i]; ++i)
    {
        if (s[i] == '0') suma--;
        else suma++;
        st[suma] = min(st[suma], i);
        dr[suma] = max(dr[suma], i);
        vmin = min(vmin, suma);
        vmax = max(vmax, suma);
    }

    /// lungimea maxima a secventei
    lgMax = 0;
    for (i = vmin; i < vmax; i++)
        lgMax = max(lgMax, dr[i+1] - st[i]);

    /// numarul de aparitii ale secventei maximale
    int s0, s1;
    s0 = s1 = suma = 0;
    for (i = 1; i <= lgMax; ++i)
        if (s[i] == '0') s0++;
        else s1++;
    if (s1 > s0) suma++;
    for (i = lgMax + 1; s[i]; ++i)
    {
        if (s[i-lgMax] == '0') s0--;
        else s1--;
        if (s[i] == '0') s0++;
        else s1++;
        if (s1 > s0) suma++;
    }

    if (optiune == 1)
        fout << lgMax << "\n";
    else fout << suma << "\n";
    fout.close();
    fin.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 #1143 Dominant

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