Cod sursa(job #4703)

Utilizator judy_kCristina Petrovici judy_k Data 6 ianuarie 2007 12:35:33
Problema Farfurii Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <stdio.h>

long long n,i,j,l,k,m,a[100010],b[100010];

long long caut(int l,int r,int n)
{
	int m,sol=0;
 	while (l<=r)
    {
    	m=(l+r)/2;
        if (m*(m+1)/2==n)
        {
         	sol=m;
            break;
        }
        else
        if (m*(m+1)/2<n && (m+1)*(m+2)/2>n)
        {
         	sol=m+1;
            break;
        }
        else
        if (m*(m+1)/2<n) l=m+1;
        else r=m-1;
    }
    return sol;
}


int main()
{
	freopen("farfurii.in","r",stdin);
    freopen("farfurii.out","w",stdout);
    scanf("%lld %lld",&n,&m);

    for (i=1;i<=n;++i) b[i]=0;
    k=caut(1,n,m);
    j=(k*(k+1))/2-m;
    l=n;
    for (i=k;i>0;--i)
    	if (i!=j)
        {
         	a[l]=n-i;
            l--;
            b[a[l+1]]=1;
        }
    a[l]=n;
    if (j>0)
    {
     	l--;
        a[l]=n-j;
        b[a[l]]=1;
    }
    j=0;
    for (i=1;i<n;++i)
    	if(b[i]==0)
        {
         	j++;
            a[j]=i;
        }

    for (i=1;i<=n;++i)
    	printf("%lld ",a[i]);

    return 0;
}