Pagini recente » Cod sursa (job #2909788) | Cod sursa (job #2672128) | Cod sursa (job #1302335) | Cod sursa (job #2047489) | Cod sursa (job #7315)
Cod sursa(job #7315)
#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;
}