Fişierul intrare/ieşire:ciurulet.in, ciurulet.outSursăONI 2016, Baraj
AutorAdrian BudauAdăugată devladrochianVlad Rochian vladrochian
Timp execuţie pe test0.35 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Ciuruleț

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.
  • Orice şir din care se obţine şirul notat pe foaie în urma aplicării algoritmului de mai sus şi care conţine un număr maximal de 1 va fi considerat corect.
  • Cele două şiruri sunt indexate de la poziţia 2.

Exemplu

ciurulet.inciurulet.outExplicaţii
6
10??0
4
10111
Transformările prin care şirul 10111 va trece sunt:
10111 -> 10011 -> 10010
9
??10?00?
5
01101011
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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?