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;
Exemple
blis.in
blis.out
Explicaţii
4
1001110111101010011
15
6
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