Cod sursa(job #2129836)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 13 februarie 2018 10:12:31
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <bitset>
#define MOD 194767
using namespace std;
int d[2][32897];
int modul (int x){
    if (x>=0)
        return x;
    return -x;
}
int main()
{
    FILE *fin=fopen ("1-sir.in","r");
    FILE *fout=fopen ("1-sir.out","w");
    int n,s,i,j,t,smax;
    fscanf (fin,"%d%d",&n,&s);
    smax=n*(n+1)/2;
    if (s<-smax || s>smax){
        fprintf (fout,"0");
        return 0;
    }
    /// d[i][j] = cate siruri de lung i cu suma j
    d[0][0]=1;
    t=1;
    for (i=2;i<=n;i++){
        for (j=0;j<=i*(i-1)/2;j++){
            // la un 1-sir de i-1 elem, pot sa adun 1 sau -1 la toate elem si sa pun 0 in fata, si obtin un sir
            // de lungime i
            d[t][j]=(d[1-t][modul(j-(i-1))]+d[1-t][j+i-1])%MOD;
        }
        t=1-t;
    }
    fprintf (fout,"%d",d[1-t][s]);
    return 0;
}