Fișierul intrare/ieșire	blis.in, blis.out	Sursă	OJI 2012, clasele 11-12
Autor	Dan Pracsiu	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.2 sec	Limită de memorie	36864 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Blis (clasele 11-12)

Se consideră un șir de biți și un număr natural K. Șirul se împarte în secvențe astfel încât fiecare bit din șir să aparțină unei singure secvențe și fiecare secvență să aibă lungimea cel puțin 1 și cel mult K. După împărțire, fiecare secvență de biți se convertește în baza 10, obținându-se un șir de valori zecimale. De exemplu, pentru șirul de biți 1001110111101010011 și K = 4, se poate obține 1 0011 101 111 0 1010 011, apoi în baza 10: 1, 3, 5, 7, 0, 10, 3. O altă împărțire poate fi 1 00 1 1 10 11 110 1010 011, adică 1, 0, 1, 1, 2, 3, 6, 10, 3.

Cerință

Scrieți un program care:

• determină valoarea maximă (în baza 10) care se poate obține dintr-o secvență de cel mult K biți
• împarte șirul inițial în secvențe de cel mult K biți astfel încât șirul zecimal obținut să conțină un subșir strict crescător de lungime maximă posibilă.

Date de intrare

Prima linie a fișierului de intrare blis.in conține numărul natural K, iar pe linia a doua se află șirul de biți, șirul neconținând spații.

Date de ieșire

Fișierul de ieșire blis.out va conține pe prima linie un număr natural reprezentând valoarea maximă care se poate obține dintr-o secvență de cel mult K biți, iar pe linia a doua un singur număr natural reprezentând lungimea maximă a subșirului strict crescător care se poate obține din șirul de biți prin împărțirea sa în secvențe de cel mult K biți.

Restricții

• 3 ≤ lungimea șirului de biți ≤ 100 000
• pentru 70% din teste, lungimea șirului de biți ≤ 1000
• 1 ≤ K ≤ 30
• Un subșir se obține dintr-un șir prin eliminarea a zero, unul, două sau mai multe elemente;
• O secvență este formată din elemente aflate pe poziții consecutive în șir;
• Pentru rezolvarea corectă a primei cerințe se acordă 20% din punctaj, iar pentru rezolvarea corectă a celei de-a doua se acordă 80%.

Exemplu