Cod sursa(job #590636)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 18 mai 2011 22:11:43
Problema Grupuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <cstdio>

using namespace std;

long long N, K, A[100005], AMax, NGrupuri;

void Read ()
{
	FILE *fin = fopen ("grupuri.in", "r");
	long long i;
	fscanf (fin, "%lld%lld", &K, &N);
	for (i=0; i<N; i++)
	{
		fscanf (fin, "%lld", &A[i]);
		if (A[i]>AMax)
		{
			AMax=A[i];
		}
	}
	fclose (fin);
}

void Type ()
{
	FILE *fout = fopen ("grupuri.out", "w");
	fprintf (fout, "%lld\n", NGrupuri);
	fclose (fout);
}

inline long long Min (long long a, long long b)
{
	if (a>b)
	{
		return b;
	}
	return a;
}

int Possible (long long G)
{
	long long i, NAnimale=0;
	for (i=0; i<N; i++)
	{
		NAnimale+=Min(A[i], G);
	}
	if (NAnimale/G>=K)
	{
		return 1;
	}
	return 0;
}

int main ()
{
	long long Left, Right, Middle;
	Read ();
	Left=1;
	Right=AMax*N+10;
	while (Left<=Right)
	{
		Middle=(Left+Right)/2;
		if (Possible (Middle)==1)
		{
			Left=Middle+1;
			NGrupuri=Middle;
		}
		else
		{
			Right=Middle-1;
		}
	}
	Type ();
	return 0;
}