== include(page="template/taskheader" task_id="blis") ==
Poveste și cerință...
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
...
|_. 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") ==
