Cod sursa(job #7315)

Utilizator flo_demonBunau Florin flo_demon Data 21 ianuarie 2007 13:25:25
Problema 1-sir Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasele 11-12 Marime 1.15 kb
#include <stdio.h>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

int l, sum;
int total;
vector<map<int, map<int, int> > > a;

int howMany(int n, int s, int last);

int main()
{
    FILE *fin = fopen("1-sir.in", "r");
    fscanf(fin, "%d%d", &l, &sum);
    fclose(fin);
    a.resize(l+4);
    
    for (int i = 0; i <= 10000; ++i)
        a[0][i][sum] = 1;
    FILE *fout = fopen("1-sir.out", "w");
    if ((((l-1)*l) / 2) > abs(sum))
        fprintf(fout, "0\n");
    else
    {
        total = howMany(l-1, 0, 0);
        fprintf(fout, "%d\n", total);
    }
    fclose(fout);
    
    return 0;
}

int howMany(int n, int s, int last)
{
    int rez = 0;
    if (n < 0) return 0;
    if (s > sum) return 0;
    if (s < -sum) return 0;
    if (a[n][last].count(s)) 
    { 
        return (a[n][last][s] % 194767); 
    }
    else
    {
        rez += howMany(n-1, s + (last-1), last-1);
        if (rez > 194767)
            rez %= 194767;
        rez += howMany(n-1, s + (last+1), last+1);
        if (rez > 194767)
            rez %= 194767;
    }
    a[n][last][s] = rez;
    return rez;
}