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ța

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

Fișierul de intrare blis.in conține pe prima linie 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;

Exemplu

blis.in

4
1001110111101010011

blis.out

15
6

Explicație

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Blis:

//Solutia oficiala - implementare STL
//100 puncte
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
#include<vector>
#define N 100010
using namespace std;
int n,k,K,i,j,v,big,ST,DR,MI,BST[N];
int oo=(1<<30)+100;
vector< pair<int,int> > UPD[N];
char B[N];
int main()
{
    freopen("blis.in","r",stdin);
    freopen("blis.out","w",stdout);
    scanf("%d%s",&k,B+1);n=strlen(B+1);
    for(i=1;i<=n+1;i++)BST[i]=oo;BST[0]=-1;
    for(i=1;i<=n;i++)
    {
        v=0;K=min(n,i+k-1);
        for(j=i;j<=K;j++)
        {
            v=(v<<1)|(B[j]-'0');big=max(big,v);
            for(ST=0,DR=i+1;DR-ST-1;)
            {
                MI=(ST+DR)/2;
                if(BST[MI]<v)ST=MI;
                else DR=MI;
            }
            if(BST[DR]>v)UPD[j].push_back(make_pair(DR,v));
        }
        for(vector< pair<int,int> >::iterator it=UPD[i].begin();it!=UPD[i].end();it++)
            if(BST[it->first]>it->second)
                BST[it->first]=it->second;
    }
    printf("%d\n",big);
    for(ST=0,DR=n+1;DR-ST-1;)
    {
        MI=(ST+DR)/2;
        if(BST[MI]<oo)ST=MI;
        else DR=MI;
    }
    printf("%d\n",ST);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1035 Blis

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1035 Blis de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1035 Blis