Cod sursa(job #1496206)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 4 octombrie 2015 16:16:33
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int MX = 40000;
const int MD = 194767;

int Nextint()
{
    char S[100];
    int Num = 0,i = 0;
    bool Neg = 0;

    scanf("%s",S);

    if (S[0] == '-')
        Neg = 1,i++;

    for (;i < strlen(S);i++)
        Num = Num * 10 + (S[i] - '0');

    if (Neg)
        Num *= -1;

    return Num;
}

int abs(int X)
{
    if (X < 0)
       return -X;

    return X;
}

int N,S,aux;
int DP[2][MX];

int main()
{
    freopen("1-sir.in","r",stdin);
    freopen("1-sir.out","w",stdout);

     N = Nextint();
     S = Nextint();

     DP[0][0] = 1;

     for (int i = 2;i <= N;i++)
     {
         aux = !aux;

         int M = i * (i - 1) / 2;

         for (int j = 0;j <= M;j++)
             DP[aux][j] = (DP[!aux][abs(j + i - 1)] + DP[!aux][abs(j - i + 1)]) % MD;
     }

     printf("%d\n",DP[aux][abs(S)]);

  return 0;
}