Cod sursa(job #1520083)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 8 noiembrie 2015 12:12:56
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<fstream>

using namespace std;

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

const int nmax = 256;
const int mod = 194767;
const int smax = nmax * (nmax - 1) / 2 + 1;
int d[ 2 ][ 2 * smax + 1 ];

int main() {
    int n, s;
    fin >> n >> s;
    if ( s > (n - 1) * n / 2 || s < -n * (n - 1) / 2 ) {
        fout << "0\n";
    } else {
        int ind = 0;
        d[ 1 ][ smax + 0 ] = 1;
        for( int i = 2; i <= n; ++ i, ind = 1 - ind ) {
            for( int j = -i * (i - 1) / 2; j <= (i - 1) * i / 2; ++ j ) {
                if ( j + smax - (i - 1) >= 0 ) {
                    d[ ind ][ j + smax ] += d[ 1 - ind ][ j + smax - (i - 1) ];
                }
                if ( j + smax + (i - 1) <= 2 * smax ) {
                    d[ ind ][ j + smax ] += d[ 1 - ind ][ j + smax + (i - 1) ];
                }

                if ( d[ ind ][ j + smax ] >= mod ) {
                    d[ ind ][ j + smax ] -= mod;
                }
            }
        }
        fout << d[ 1 - ind ][ s + smax ] << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}