Cerința

Se dau două numere naturale N şi K. Determinaţi numărul de şiruri de lungime N formate doar din semnele + şi – şi în care nu apar K semne – pe poziţii consecutive.

Date de intrare

Fișierul de intrare minusk.in conţine pe prima linie 2 numere naturale separate printr-un spaţiu, N şi K, cu semnificaţia din enunţ.

Date de ieșire

Fișierul de ieșire minusk.out va conține pe prima linie un singur număr natural reprezentând valoarea cerută, modulo 2011.

Restricții și precizări

1 ≤ K ≤ N ≤ 1000000;
pentru 30% dintre teste N ≤ 10
pentru 70% dintre teste N ≤ 1000

Exemplu

minusk.in

4 2

minusk.out

Explicație

Cele 8 şiruri sunt: ++++, +++-, ++-+, +-++, -+++, +-+-, -++-, -+-+. În niciunul dintre aceste şiruri nu avem două sau mai mult de două caractere – pe poziţii consecutive.

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

#include <stdio.h>
#define DIM 1000002
#define MOD 2011

int P[DIM];
int M[DIM];
int N, K, T, i, aux;

int main() {
    FILE *f = fopen("minusk.in","r");
    fscanf(f,"%d %d",&N, &K);
    fclose(f);
    P[0] = 1;
    P[1] = 1;
    M[1] = 1;
    for (i=2;i<=N;i++) {
        P[i] = (P[i-1] + M[i-1]) % MOD;
        if (i>=K)
            aux = P[i-K];
        else
            aux = 0;
        M[i] = (P[i-1] + M[i-1]) % MOD;
        M[i] -= aux;
        if (M[i]<0)
            M[i]+=MOD;
    }
    FILE *g = fopen("minusk.out","w");
    fprintf(g,"%d",(P[N] + M[N])%MOD);
    fclose(g);

}

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 #730 MinusK

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