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.

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>