Cod sursa(job #568033)

Utilizator Catah15Catalin Haidau Catah15 Data 30 martie 2011 19:05:31
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>

using namespace std;

#define LL long long
#define maxN 100005


LL N, M;
bool ok;


int bin_Search ()
{
	int st = 0, dr = maxN, mid;
	
	while (st <= dr)
	{
		mid = (st + dr) / 2;
		
		if ( M == (mid * (LL) (mid - 1) / 2) )
		{
			ok = true; 
			return mid;
		}
		
		if ( mid * (LL) (mid - 1) / 2 > M && (mid - 1) * (LL) (mid - 2) / 2 < M )
			return mid;
		else
		if ( (mid * (LL) (mid - 1) / 2) > M)
			dr = mid - 1;
		else
			st = mid + 1;
	}

	return 0;
}


int main()
{
	ifstream f("farfurii.in");
	ofstream g("farfurii.out");
	
	f >> N >> M;
	
	int x = bin_Search ();
	
	
	for (int i = 1; i <= N - x; ++ i)
		g << i << " ";
	
	if (ok)
	{
		for (int i = N; i >= N - x + 1; -- i)
			g << i << " ";
		
		return 0;
	}
	
	LL e = ( x * (LL) (x - 1) / 2 ) - M;
	e = N - e;
	
	g << e << " ";
	
	for (int i = N; i >= N - x + 1; -- i)
	{
		if (i == e) continue;
		
		g << i << " ";
	}
	
	
	f.close();
	g.close();
	
	return 0;
}