Editing 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 <code>1</code> este strict mai mare decât numărul valorilor de <code>0</code>. De exemplu, în șirul <code>1,0,0,0,1,1,0,1,1,1,0,0</code> o secvență dominantă este <code>0,1,1</code> și o alta, de lungime mai mare, este <code>0,1,1,0,1,1,1</code>. Secvența dominantă maximală este secvența dominantă de lungime maximă. În șirul din exemplu secvența dominantă maximală este <code>1,0,0,0,1,1,0,1,1,1,0</code> (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 <code>dominant.in</code> conține pe prima linie un număr natural <code>V</code>, iar pe linia a doua șirul de valori binare, fără spații.

= Date de ieșire =
Fișierul de ieșire <code>dominant.out</code> va conține:

* varianta 1: dacă <code>V=1</code>, 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ă <code>V=2</code>, 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 =

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

= Exemplul 1 =
<code>dominant.in</code>
 1
 100011011100
<code>dominant.out</code>
 11

= Explicație =
Secvența dominantă maximală este <code>10001101110</code> și are lungimea <code>11</code>.

= Exemplul 2 =
<code>dominant.in</code>
 2
 100011011100
<code>dominant.out</code>
 1

= Explicație =
Secvența dominantă maximală este <code>10001101110</code> și are lungimea <code>11</code>. Este o singură secvență dominantă maximală.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

Nmax = 300005
inFile = "dominant.intxt"
outFile = "dominant.outtxt"

s = [''] * Nmax
x = [0] * (2*Nmax)
y = [0] * (2*Nmax)
st = None
dr = None
optiune = 0

def main():
    global s, optiune, st, dr
    i = 0
    n = 0
    suma = 0
    vmin = 0
    vmax = 0
    lgMax = 0

    # citire
    fin = open(inFile, 'r')
    fout = open(outFile, 'w')
    optiune = int(fin.readline())
    s = '*' + fin.readline().strip()

    s[0] = '*'
    n = len(s[1:])

    suma = 0
    for i in range(1, n+1):
        if s[i] == '1':
            suma += 1
        else:
            suma -= 1
    if suma > 0:
        if optiune == 1:
            fout.write(str(n) + "\n")
        else:
            fout.write("1\n")
        fout.close()
        return 0

    st = x[Nmax:]
    dr = y[Nmax:]

    # initializare st si dr
    for i in range(-n, n+1):
        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 in range(1, n+1):
        if s[i] == '0':
            suma -= 1
        else:
            suma += 1
        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 in range(vmin, vmax):
        lgMax = max(lgMax, dr[i+1] - st[i])

    # numarul de aparitii ale secventei maximale
    s0 = 0
    s1 = 0
    suma = 0
    for i in range(1, lgMax+1):
        if s[i] == '0':
            s0 += 1
        else:
            s1 += 1
    if s1 > s0:
        suma += 1
    for i in range(lgMax+1, n):
        if s[i-lgMax] == '0':
            s0 -= 1
        else:
            s1 -= 1
        if s[i] == '0':
            s0 += 1
        else:
            s1 += 1
        if s1 > s0:
            suma += 1

    if optiune == 1:
        fout.write(str(lgMax) + "\n")
    else:
        fout.write(str(suma) + "\n")
    fout.close()
    fin.close()
    return 0

if __name__ == "__main__":
    main()
</syntaxhighlight>