Cod sursa(job #2490749)

Utilizator victorv88Veltan Victor victorv88 Data 10 noiembrie 2019 20:27:41
Problema Pod Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
using namespace std;

ifstream f("pod.in");
ofstream g("pod.out");

unordered_map<int,bool>imposibil;

const int mod=9901;

int n, m, k,x, auxk;
int dp[25];

void solve()
{
    dp[0]=1;
    for (int i=1; i<=n; ++i)
    {
        if (imposibil[i])
            dp[i%auxk]=0;
        else
        {
            dp[i%auxk]=0;
            if (i-k>=0)
            {
                dp[i%auxk]+=dp[(i-k)%auxk];
            }
            dp[i%auxk]+=dp[(i-1)%auxk];
            dp[i%auxk]%=mod;
        }
        imposibil.erase(i);
    }
    g << dp[n%auxk];
}

int main( )
{
    f >> n >> m >> k;
    for (int i=1; i<=m; ++i)
    {
        f >> x;
        imposibil[x]=true;
    }
    auxk=k+1;

    solve();
    return 0;
}