Cod sursa(job #2292070)

Utilizator vnedelcuVictor Andrei Nedelcu vnedelcu Data 28 noiembrie 2018 22:19:24
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>

const int MOD =  194767;
const int MAX = 1 << 15;

int a[2][MAX];
///a[i][j] = nr de 1-siruri de lungime i care au suma j
///a[i][j] = a[i][-j]

int abs(int x)
{
    return ((x < 0) ? -x : x);    
}

int main()
{
    FILE *f;
    int N,S,n,i,j;
    
    f = fopen("1-sir.in","r");
    fscanf(f,"%d%d",&N,&S);
    fclose(f);
    
    n = N*(N-1)/2;
    int p_row = 0;
    int c_row = 1;
    a[0][0] = 1;
    for (i = 2; i <= N; i++)
    {
        int m = i*(i-1)/2;
        for (j = 0; j <= m; j++)
        {
            /// 0|0... => 0|1...
            /// 0... are suma S si lungime K => 0... + K are suma S+K si lungime K
            /// 0|0... => 0|-1...
            /// 0... are suma S si lungime K => 0... - K are suma S-K si lungime K
            a[c_row][j] = a[p_row][abs(j - i + 1)];
            if ((j + i - 1) <= m) 
                a[c_row][j] += a[p_row][j + i - 1];
            a[c_row][j] %= MOD;
        }
        p_row = 1 - p_row;
        c_row = 1 - c_row;
    }
    
    f = fopen("1-sir.out","w");
    if (abs(S) > n)
        fprintf(f,"0");
    else
        fprintf(f,"%d",a[p_row][abs(S)]);
    
    return 0;
}