Cod sursa(job #13556)

Utilizator megabyteBarsan Paul megabyte Data 6 februarie 2007 23:43:04
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#define INF "farfurii.in"
#define OUF "farfurii.out"
#define NMAX 131072
int main()
{
	unsigned long long n,k,i,aux,p,q,mij,nr,sol[NMAX];
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	fscanf(in,"%lld %lld",&n,&k);
	p=1;q=n;
	while(p<=q)
	{
		mij=(p+q)/2;
		aux=mij*(mij-1)/2;
		if(aux<k) p=mij+1;
		else if(aux>k) q=mij-1;
		else break;
	}
	while((mij*(mij-1)/2)>=k) mij--;
	while((mij*(mij-1)/2)<k) mij++;
	q=mij*(mij-1)/2;
	//printf("%lld\n",)
	mij=n-mij;
	//printf("%d ",mij);
	for(i=1;i<=mij;i++) sol[i]=i;
	nr=n;
	for(i=mij+1;i<=n;i++) {sol[i]=nr;nr--;}
        //q=mij*(mij-1)/2;
	p=q-k+mij+1;
//        printf("%lld %lld %lld \n",p,q,k);
        if(p>n) p=mij+1;
	aux=sol[p];
	for(i=p;i>mij+1;i--) sol[i]=sol[i-1];
	sol[mij+1]=aux;
	for(i=1;i<=n;i++) fprintf(out,"%d ",sol[i]);
	fclose(in);fclose(out);
	return 0;
}