Cod sursa(job #290853)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 28 martie 2009 20:57:43
Problema Grupuri Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include<stdio.h>
long n,k;
long long s;
long v[100010];

void read()
{
	freopen("grupuri.in","r",stdin);
	freopen("grupuri.out","w",stdout);
	scanf("%ld%ld",&k,&n);
	for(long i=1;i<=n;i++)
	{
		scanf("%ld",&v[i]);
		s+=v[i];
	}
}

int exista(long long m)
{
	long i;
	long long suma=0;
	for(i=1;i<=n;i++)
	{
		if(v[i]>=m)
			break;
		suma=suma+v[i];
	}
	suma=suma+(n-i+1)*m;
	return suma>=m*k;
}

void cautare()
{
	long long st=1,dr=s/k,m;
	while(st!=dr)
	{
		m=(st+dr)/2;
		if(exista(m))
			st=m+1;
		else
			dr=m;
	}
	printf("%lld",st);
}

int main()
{
	read();
	cautare();
	return 0;
}