Pagini recente » Cod sursa (job #2548522) | Cod sursa (job #718092) | Cod sursa (job #2962995) | Cod sursa (job #2323805) | Cod sursa (job #1416701)
#include<cstdio>
#include<cstring>
using namespace std;
struct TRIPLE
{
int prev, adag, deadag;
};
int v[19], ans[19][19];
TRIPLE d[1000000];
inline void genv(int n)
{
register int i, j, k;
int tr[19][19];
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
for(k=1; k<=n; k++)
tr[j][k]=0;
tr[1][i]=1;
v[i]=1;
for(j=2; j<=n; j++)
for(k=1; k<=n-j+1; k++)
{
tr[j][k]=tr[j-1][k+1]+tr[j-1][k];
v[i]+=tr[j][k];
}
}
}
inline void recon(int n, int s)
{
register int i, j;
for(i=1; i<=n; i++)
ans[1][i]=1;
i=s;
while(d[i].prev!=-1)
{
ans[1][d[i].adag]+=d[i].deadag;
i=d[i].prev;
}
for(i=2; i<=n; i++)
for(j=1; j<=n-i+1; j++)
ans[i][j]=ans[i-1][j]+ans[i-1][j+1];
}
int main()
{
FILE *in, *out;
in=fopen("triunghi.in", "r");
out=fopen("triunghi.out", "w");
register int n, s, i, sum, smax;
fscanf(in, "%d%d", &n, &s);
smax=0;
sum=0;
genv(n);
for(i=1; i<=n; i++)
sum+=v[i];
if(sum>s)
{
fprintf(out, "imposibil");
return 0;
}
register int mul, j;
smax=sum;
d[smax].prev=-1;
d[smax].adag=0;
d[smax].deadag=0;
for(i=1; i<=n/2+n%2&&(!d[s].prev); i++)
{
for(j=smax; j>=sum&&(!d[s].prev); j--)
{
if(d[j].prev)
{
mul=1;
while(j+v[i]*mul<=s)
{
if(!d[j+v[i]*mul].prev)
{
d[j+v[i]*mul].prev=j;
d[j+v[i]*mul].adag=i;
d[j+v[i]*mul].deadag=mul;
if(j+v[i]*mul>smax)
smax=j+v[i]*mul;
}
mul++;
}
}
}
}
if(!d[s].prev)
{
fprintf(out, "imposibil");
}
else
{
recon(n, s);
for(i=n; i>=1; i--)
{
for(j=1; j<=n-i+1; j++)
fprintf(out, "%d ", ans[i][j]);
fprintf(out, "\n");
}
}
return 0;
}