blis

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 şi precizări

• 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

blis.in

4
1001110111101010011

blis.out

15
6

Explicații

Secvenţa de valoare maximă de cel mult 4 biţi este 1111, adică 15 în baza 10.
Pentru cerinţa a doua, şirul binar se împarte astfel:
1 00 1 1 10 11 110 1010 011,
Se obţine şirul zecimal:
1, 0, 1, 1, 2, 3, 6, 10, 3.
Subşirul strict crescător maximal de lungime 6 este 0, 1, 2, 3, 6, 10