Cod sursa(job #254746)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 7 februarie 2009 13:57:32
Problema Planeta Scor 40
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 2 Marime 1.18 kb
#include <stdio.h>
int a[100][100];
int v[100];
int n, m, i, j,k;
inline int min(int a, int b)
{
	if (a > b)
		return a;
	return b;
}
void solve(int l, int p, int q)
{
	int s= 0, i;
	if (l <= 0)
		return;
	if ( m <=0)
		return;
	for (i = 1; i <= l; ++ i)
	if (!v[i+p])
	{
		s+=a[l][i]*q;
		if (s >= m)
		{
			s-=a[l][i]*q;
			break;
		}
	}
	
	/*while (v[i+p])
		--i;
	*/	
	printf("%d ", (i)+p);
	v[i+p] = 1;
	m -= s;
	int o;
	int sol1 = 0;
	for (o = 1; o < i; ++ o)
		sol1+=a[i-1][o];
	int sol2 = 0;
	for (o= i+1; o <=l; ++ o)
		sol2+=a[l-i][o-i];

	sol1 = min(sol1,1);
	sol2 = min(sol2,1);
	

	solve(i-1,p, q*sol2);
	solve(l-i,p+i,q);
}
int main()
{
	freopen("planeta.in","r",stdin);
	freopen("planeta.out","w",stdout);
	scanf("%d %d", &n, &m);
	a[1][1] = 1;
	for (i = 1; i <= n; ++ i)
		a[1][i] = 1;
	for (i = 2; i <= n; ++ i)
	{
		for (j = 1; j <= i; ++ j)
		{
			int sol1 = 0;
			for (k = 1; k < j; ++ k)
				sol1+=a[j-1][k];
			int sol2 = 0;
			for (k= j+1; k <=i; ++ k)
				sol2+=a[i-j][k-j];
			
			sol1 = min(sol1,1);
			sol2 = min(sol2,1);
			a[i][j] = sol1*sol2;
			
		}
	}
	int sol = 0;
	solve(n,0,1);


	return 0;
}