Raul: Pagină nouă: 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...

2024-02-16T17:03:25Z

Pagină nouă: 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...

New page

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>

1143 - Dominant - Revision history