Cod sursa(job #564134)

Utilizator tudorsTudor Siminic tudors Data 26 martie 2011 19:40:22
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#define ll long long
using namespace std;
ll n,k,M,i,x;
FILE *f, *g;
void caut_bin()
{
	ll st,dr,mij;
	st=1;
	dr=n;
	while (st<=dr)
	{
		mij=(st+dr)/2;
		if ((long long)(mij*(mij-1)/2)<=k)
			st=mij+1;
		else
			dr=mij-1;
	}
	M=st;
}
int main()
{
	f=fopen("farfurii.in","r");
	g=fopen("farfurii.out","w");
	fscanf(f,"%lld %lld",&n,&k);
	// se cauta binar M a.i.
	// m(m-1)/2 = K
	caut_bin();
	if (1ll*M*(M-1)/2==k)
	{
		for (i=1;i<=n-M;i++)
			fprintf(g,"%lld ",i);
		for (i=0;i<M;i++)
			fprintf(g,"%lld ",n-i);
	}
	else
	{
		x=1ll*M*(M-1)/2-k;
		for (i=1;i<=n-M;i++)
			fprintf(g,"%lld ",i);
		fprintf(g,"%lld ",n-x);
		for (i=0;i<M;i++)
			if (i!=x)
				fprintf(g,"%lld ",n-i);
	}
	fclose(f);
	fclose(g);
	return 0;
}