Dorești să mergi în vacanță și ai hotărât deja destinația. Formal, te afli în punctul (0,0) al unui sistem cartezian de axe și trebuie să ajungi în punctul de coordonate (X,X). Țara în care te afli are drumuri paralele cu axele de coordonate la fiecare abscisă și la fiecare ordonată număr natural. În fiecare moment, dacă eşti în punctul de coordonate (a,b), ai 2 variante de deplasare: în punctul (a,b+1) sau în punctul (a+1,b). La fiecare astfel de pas consumi un litru de carburant. Prin unele puncte de forma (a,a) nu poți trece, iar în celelalte puncte care au abscisa egală cu ordonata poți trece și în plus, acolo se află câte o stație de benzină unde poți să „faci plinul”. Prin toate punctele care nu au abscisa egală cu ordonata poți trece dar acolo nu se află stații de benzină. Rezervorul mașinii tale are o capacitate de K litri.

Cerința

Determinați numărul de trasee distincte prin care poți ajunge la destinație. Două trasee sunt distincte dacă diferă prin cel puţin un punct.

Date de intrare

Fișierul calatorie.in conține pe prima linie două numere separate printr-un spațiu, X și K, cu semnificația din enunț.
Pe linia a 2-a se găsește un număr N, care reprezintă numărul de puncte de forma (a,a) care nu pot fi traversate. Pe fiecare dintre următoarele N linii se află câte un număr a, cu semnificația că punctul (a,a) nu poate fi vizitat.

Date de ieșire

Fișierul calatorie.out conține pe prima linie un singur număr natural reprezentând valoarea cerută, modulo 997.

Restricții și precizări

1 ≤ X ≤ 50000
2 ≤ K ≤ 50
0 ≤ N ≤ 10
Călătoria începe cu rezervorul plin;
Se garantează că există cel puțin un drum.

Exemplu

Intrare

3 10
1
1

Ieșire

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

// 100 p
#include <fstream>
#define MOD 997
#define DIMX 50010
#define DIMK 53
#define INF 1<<30

using namespace std;

int c[DIMK];
int b[DIMX];
int d[DIMX];

int a, x, k, i, j, n;

inline int maxim(int a, int b) {
    return (a > b ? a : b);
}

int main() {
    ifstream fin("calatorie.in");
    ofstream fout("calatorie.out");
    fin>>x>>k;
    if (k%2 == 1)
        k--;
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>a;
        if (a < x)
            b[a] = 1;
    }
    c[0] = 1;
    for (i=1;i<=k;i++) {
        c[i] = 0;
        for (j=0;j<i;j++) {
            c[i] += c[j]*c[i-j-1];
            c[i] %= MOD;
        }

    }

    d[0] = 1;
    for (i=1;i<=x;i++)
        if (b[i])
            d[i] = INF;
        else {
            for (j=maxim(i-k/2,0);j<i;j++)
                if (!b[j]) {
                    d[i] += 2*d[j]*c[i-j-1];
                    d[i] %= MOD;
                }
        }
    fout<<d[x]<<"
";
    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 #679 calatorie

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