Rezolvare completă PbInfo #1712 Centura

Pe șoseaua care duce spre intrarea în oraș se află n autovehicule, dintre care m
sunt autovehicule de gabarit redus, pe care le vom numi în continuare autoturisme, iar restul sunt de gabarit mare și le vom numi camioane. Orașul are o șosea ocolitoare, numită popular centură. Camioanele trebuie să ocolească orașul
trecând în mod obligatoriu pe drumul de centură. Autoturismele pot continua drumul pe șoseaua care intră în oraș sau pot ocoli orașul intrând pe șoseaua de centură. Pe centură, camioanele circulă cu viteză redusă îngreunând traficul.

De aceea s-a impus restricția R: nu vor fi admise pe drumul de centură coloane formate din mai mult decât k camioane consecutive.

Cerința

Cunoscând n, k și distribuția autovehiculelor pe șosea, să se determine două numere naturale V și T, unde V reprezintă numărul de variante de dirijare a traficului astfel încât să fie respectată restricția R, iar T reprezintă numărul minim de autoturisme care trebuie să fie deviate pe drumul de centură pentru a se respecta aceeași restricție R.

Date de intrare

Fișierul de intrare centura.in conține pe prima linie trei numere naturale nenule n m k. Pe următoarea linie un șir de caractere format doar din caracterele A și C. Caracterul A reprezintă un autoturism, iar caracterul C reprezintă un camion.

Date de ieșire

Fișierul de ieșire centura.out va conține pe prima linie numerele naturale nenule V și T separate prin spațiu, cu semnificația din enunț.

Restricții și precizări

  • 1 ≤ k < n ≤ 100000
  • 1 < m ≤ 30
  • Atenție, dacă inițial avem un șir de forma CCAAC și k=2, atunci sunt două soluții distincte pentru mersul pe centură: CCAC (primul A merge prin oraș) și din nou CCAC (al doilea A merge prin oraș).
  • Se garantează că, pentru toate datele de test, șirul inițial de autovehicule respectă restricția R.

Exemplul 1

centura.in

8 3 2
CCAACACC

centura.out

3 2

Explicație

Sunt posibile următoarele trei variante de separare a coloanei inițiale de autovehicule:

  1. prin oraș: A1; pe centură: C1C2A2C3A3C4C5
  2. prin oraș: A2; pe centură: C1C2A1C3A3C4C5
  3. prin oraș: nici unul; pe centură: C1C2A1A2C3A3C4C5 (toate)

Este necesar ca minimum două autoturisme să fie deviate pe drumul de centură. Prin urmare: V = 3 și T = 2.

Exemplul 2

centura.in

7 2 2
CCACCAC

centura.out

1 2

Explicație

Există o singură variantă: toate autovehiculele vor fi deviate pe drumul de centură: C1C2A1C3C4A2C5 Prin urmare: V = 1 și T = 2.

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 Centura:

/* Mihail Cosmin Pit-Rada
    O(m)
*/
#include<fstream>
using namespace std;
ifstream  fin("centura.in");
ofstream fout("centura.out");

int n, m, k, poz[10002], b[10002], s[10002];
char ch;

int main(){
    fin>>n>>m>>k;
    int i,j;
    j=0;
    for(i=1;i<=n;i++){
        fin>>ch;    if(ch=='A') poz[++j]=i;
        ///in poz[] se pastreaza pozitiile autoturismelor relativ la sirul citit
    }
    poz[m+1]=n+1; ///am introdus un autoturism fictiv la pozitia n+1

    ///b[i]=numarul minim de autoturisme dintre 1...i care trebuie deviate pe centura
    ///s[i]-s[i-1]=numarul de variante de dirijare care respecta restrictia R utilizand 1...i
    ///in prima etapa analizez calculez prefixul care contine cel mult k camioane
    b[0]=0;
    s[0]=1;
    for(i=1;i<=m+1 && poz[i]-i<=k;i++){
        s[i]=(s[i-1]*2);
        b[i]=1;
    }
    ///continuam calculul si pentru restul sirului
    ///b[i] si s[i] vor fi influentate doar de "istoria" data de secventa cu ultimele cel mult k camioane
    ///s[i-1]-s[j-1] reprezinta numarul solutiilor valabile pentru pozitia i si care trebuie adaugate la s[i-1]
    ///s[i]=s[i-1]+(s[i-1]-s[j-1]);
    j=0;
    for(;i<=m+1;i++){
        while(poz[i]-poz[j]-i+j>k) j++;
        ///am actualizat secventa maximala delimitata la dreapta de autoturismul i si care contine cel mult k
        ///camioane; secventa este cuprinsa intre autoturimele j si i, inclusiv
        ///pentru ca intreaga secventa 1...i sa respecte restrictia R trebuie sa mai utilizam inca b[j] autoturisme
        s[i]=(s[i-1]*2-s[j-1]);
        b[i]=1+b[j];
    }
    fout<<(s[m+1]-s[m])<<" "<<b[m+1]-1;///am scazut autoturismul fictiv de la pozitia n+1
    fout.close();
    fin.close();
    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 #1712 Centura

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1712 Centura 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!