blis

Blis

== include(page="template/taskheader" task_id="blis") ==

Poveste şi cerinţă...

p<>. 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$.
 
h2. 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ă.
 

h2. Date de intrare

Fişierul de intrare $blis.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $blis.out$ ...

p<>. 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.

h2. 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%$.

h2. Exemplu

table(example). |_. blis.in |_. blis.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. blis.in |_. blis.out |_. Explicaţie |
| 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$
|

== include(page="template/taskfooter" task_id="blis") ==

7682