Cod sursa(job #1385677)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 12 martie 2015 11:15:53
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("1-sir.in");
ofstream fout("1-sir.out");

const int MODULO=194767;
const int SMAX=35000;

int n,S,dp[2][SMAX];

/*din sirul 0 1 2 3 4 .... n-1 vreau sa scad cate 2
din fiecare ,iar daca scad,scad si din urmatorii ca sa
se mentina ok.Inseamna ca vreau sa scad ceva din n*(n-1)/2
ca sa dea S,deci din elem de forma 2*i,1<=i<=n-1, sa aflu
nr de sume=n*(n-1)/2-S
*/

int main()
{
    int i,j,x;
    bool ok;
    fin>>n>>S;
    S=abs(S);
    S=n*(n-1)/2-S;
    if (S<0) {fout<<"0\n";return 0;}
    dp[0][0]=1;
    for (i=1,ok=1;i<n;i++,ok=1-ok)
    {
        x=2*i;
        for (j=0;j<SMAX;j++)
        {
            dp[ok][j]=dp[1-ok][j];
            if ((j-x)>=0) dp[ok][j]+=dp[1-ok][j-x];
            if (dp[ok][j]>=MODULO) dp[ok][j]-=MODULO;
        }
    }
    fout<<dp[1-ok][S]<<"\n";
    return 0;
}