Cod sursa(job #357429)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 19 octombrie 2009 11:45:09
Problema Farfurii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#define N 100001

long long n,m;

void rezolvare()
{
	long long p,val,val_modificata;
	for (p = 1; p <= n; ++p)//Daca ordonam descrescator sirul, fiecare termen al sirului se cupleaza cu toti cei de dupa el (suma combinatiilor pt fiecare nr n-1+...+1+0) , deci (n-1)(n)/2. Inlocuim n cu n-p atunci cand ne referim la numerele din sirul ramas.
		if ((n-p-1)*(n-p)/2 >= m)//Mai am spatiu de permutari.
			printf ("%d ",p);
		else
		{
			printf ("%d ",p + m - (n-p-1)*(n-p)/2); //p -> numarul care l-as fi pus oricum +               m - (n-p-1)(n-p)/2 -> cate combinatii am nevoie - cate voi obtine din restul numerelor in ordine descrescatoare = cu cat maresc numarul. Aceasta marire va mai crea combinatii egale cu marirea (nr se va cupla cu nr sarite).
			val_modificata = p + m - (n-p-1)*(n-p)/2;
			break;
		}
	val = n;
	for (++p; p <= n; ++p)
	{
		if (val == val_modificata)
			--val;
		printf ("%d ",val);
		--val;
	}
}

int main()
{
	freopen ("farfurii.in","r",stdin);
	freopen ("farfurii.out","w",stdout);
	scanf ("%d%d",&n,&m);
	rezolvare();
	return 0;
}