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

2024-06-03T15:52:41Z

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

New page

== 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>

3845 - Ciurulet - Revision history