Cod sursa(job #2127390)

Utilizator shantih1Alex S Hill shantih1 Data 10 februarie 2018 16:52:09
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("1-sir.in");
ofstream fout("1-sir.out");

int n,s,i,j,nr,rz[32900];
bool b[256][32900];
struct punct
{
	int sum, ad, niv;
}p,ve;
deque <punct> c;

int main () {
	
	fin>>n>>s;
	if(s>n*(n+1)/2)	fout<<0<<"\n";
	else
	{
		rz[0]=1;
		p.sum=0;	p.ad=0;	p.niv=1;
		c.push_back(p);
		while(c.front().niv<n)
		{
			p=c.front();
			if(p.sum+p.ad+1<=s)
			{
				ve.ad=p.ad+1;	ve.sum=p.sum+ve.ad;		ve.niv=p.niv+1;
				rz[ve.sum]+=rz[p.sum];
				if(b[ve.niv][ve.sum]==0)
				{
					b[ve.niv][ve.sum]=1;
					c.push_back(ve);
				}
			}
			if(p.sum+p.ad-1>p.sum&&p.sum+p.ad-1<=s)
			{
				ve.ad=p.ad-1;	ve.sum=p.sum+ve.ad;		ve.niv=p.niv+1;
				rz[ve.sum]+=rz[p.sum];
				if(b[ve.niv][ve.sum]==0)
				{
					b[ve.niv][ve.sum]=1;
					c.push_back(ve);
				}
				rz[p.sum]=0;
			}
			else if(b[p.niv+1][p.sum]==0)
			{
				p.niv++;
				b[p.niv][p.sum]=1;
				c.push_back(p);
			}
			c.pop_front();
		}
		fout<<rz[s]<<"\n";
	}
}