Cod sursa(job #3234184)

Utilizator RosuDragos123Rosu Dragos RosuDragos123 Data 6 iunie 2024 21:13:39
Problema 1-sir Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <map>
using namespace std;
ifstream cin("1-sir.in");
ofstream cout("1-sir.out");
const int mod=194767;
map<int,int> f;
map<int,pair<int,int>> m;
int n,s;
int main()
{
    cin>>n>>s;
    if(n==1)
    {
        if(s==0){
            cout<<1<<'\n';
            return 0;
        }
        else{
            cout<<0<<'\n';
            return 0;
        }
    }
    if(n==2)
    {
        if(s==1 || -1)
        {
            cout<<1<<'\n';
        }
        else{
            cout<<0<<'\n';
        }
        return 0;
    }
    m[0].first=1;
    m[0].second=0;
    m[1].first=1;
    m[1].second=1;
    m[-1].first=1;
    m[-1].second=-1;
    for(int i=3;i<=n;i++)
    {
        map<int,pair<int,int>> aux=m;
        m.clear();
        for(int nr=-i;nr<=i;nr++)
        {
            if(aux[nr].first)
            {
                m[nr+1].first=aux[nr].first%mod;
                m[nr+1].second=aux[nr].second+nr+1;
                f[m[nr+1].second]+=m[nr+1].first%mod;
                f[m[nr+1].second]%=mod;

                m[nr-1].first=aux[nr].first%mod;
                m[nr-1].second=aux[nr].second+nr-1;
                f[m[nr-1].second]+=m[nr-1].first%mod;
                f[m[nr-1].second]%=mod;
            }
        }
    }
    cout<<f[s]%mod<<'\n';
    return 0;
}