Editing 3845 - Ciurulet

== Cerinţa ==
Popel, elev de liceu calificat la barajul pentru Lotul Național de Informatică, tocmai a învățat ciurul lui Eratostene, pentru aflarea numerelor prime, al cărui algoritm este descris astfel:

  prim[i]=1, oricare ar fi i de la 2 la N
  pentru i de la 2 la N:
      dacă prim[i] este 1:
          pentru j de la 2*i la N din i în i:
              prim[j] = 0
Din cauza oboselii și a stresului, Popel a inițializat greșit șirul prim, punând pe unele poziții 0 în loc de 1. După ce a executat algoritmul pe șirul prim greșit inițializat, a obținut un nou șir pe care l-a notat pe o foaie de hârtie. Mai târziu, nu își mai amintea șirul inițial prim, dar mai avea șirul final pe care l-a obținut. În plus, nu mai era sigur dacă unele valori din șirul final le-a notat corect, așa că le-a marcat cu caracterul "?". Popel vă roagă să aflați un șir inițial cu proprietatea că dacă ar executa algoritmul de mai sus asupra lui, ar obține un șir care s-ar potrivi cu șirul final notat pe foaie. De asemenea, el își dorește ca șirul inițial să aibă un număr cât mai mare de cifre de 1.
== Date de intrare ==
Pe prima linie a fișierului ciurulet.in se va afla numărul N reprezentând valoarea până la care se
execută algoritmul.
Următoarea linie conține N-1 caractere din mulțimea {0, 1, ?}, fără spații între ele, reprezentând șirul notat pe foaie. Caracterul ? indică un caracter pe care Popel nu și-l mai amintește (adică Popel nu mai știe dacă acolo era 0 sau 1). Al i-lea caracter dintre acestea reprezintă valoarea lui prim[i+1]. Dacă aceasta este diferită de ?, atunci Popel și-o amintește exact. Altfel, acolo ar fi putut fi orice (0 sau 1).
== Date de ieșire ==
Pe prima linie a fișierului ciurulet.out se va afla numărul maxim de cifre de 1 care pot apărea într-un șir
inițial din care se obține un șir final care se potrivește cu cel notat pe foaie.
Pe a doua linie se vor afișa N-1 caractere din mulțimea {0, 1}, fără spații între ele, care reprezintă șirul inițial folosit.
== Restricţii şi precizări ==
* '''2 ≤ N ≤ 1.000.000.'''
* Pentru 30% din teste, șirul din fișierul de intrare nu conține caracterul ?.
* Pentru ca două șiruri A și B să se potrivească, trebuie ca A[i] și B[i] să fie egale, oricare ar fi i de la 2 la N cu B[i] diferit de ?. Cu alte cuvinte, peste 0 se potrivește 0, peste 1 se potrivește 1, iar peste ? se potrivesc atât 0, cât și 1.
* Se garantează faptul că șirul final obținut notat pe foaie este unul valid.
== Exemplu 1 ==
; ciurulet.in

  9
  ??10?00?
;ciurulet.out

  5
  01101011
== Explicație ==
Aplicând algoritmul de mai sus asupra șirului 01101011 se obține în final șirul '''01100000''', care se potrivește cu ce și-a notat Popel pe foaie.
== Exemplul 2 ==
; ciurulet.in

  9
  ??10?00?
; ciurulet.out

  5
  01101011
== Explicație ==
Aplicând algoritmul de mai sus asupra șirului 01101011 se obține în final șirul '''01100000''', care se potrivește cu ce și-a notat Popel pe foaie.
<br>



== Rezolvare ==
<syntaxhighlight lang="python" line>
def find_max_ones(N, sequence):
    max_ones = 0
    max_ones_index = 0
    current_ones = 0
    current_index = 0
    
    for i in range(N - 1):
        if sequence[i] == '1':
            current_ones += 1
        elif sequence[i] == '0':
            current_ones -= 1
        
        if current_ones > max_ones:
            max_ones = current_ones
            max_ones_index = current_index
        
        current_index += 1
    
    return max_ones, max_ones_index

def generate_initial_sequence(N, sequence):
    initial_sequence = ['0'] * N
    max_ones, max_ones_index = find_max_ones(N, sequence)
    
    current_ones = max_ones
    for i in range(max_ones_index, -1, -1):
        if sequence[i] == '?':
            initial_sequence[i] = '1'
            current_ones -= 1
        elif sequence[i] == '0':
            current_ones += 1
    
    for i in range(max_ones_index + 1, N):
        if sequence[i - 1] == '?':
            initial_sequence[i] = '1'
        elif sequence[i - 1] == '1':
            initial_sequence[i] = '1' if current_ones > 0 else '0'
            current_ones -= 1
    
    return ''.join(initial_sequence)

def main():
    with open("ciurulet.in", "r") as fin:
        N = int(fin.readline())
        sequence = fin.readline().strip()
    
    max_ones, _ = find_max_ones(N, sequence)
    initial_sequence = generate_initial_sequence(N, sequence)
    
    with open("ciurulet.out", "w") as fout:
        fout.write(str(max_ones) + "\n")
        fout.write(initial_sequence)

if __name__ == "__main__":
    main()

</syntaxhighlight>