Cod sursa(job #637154)

Utilizator George25Raduta George Cristian George25 Data 20 noiembrie 2011 12:24:37
Problema Zombie Scor 100
Compilator cpp Status done
Runda .com 2011 Marime 0.86 kb
#include<stdio.h>
long long i,n,a[1000002],suma,raspuns,t1,d,k,sum;

inline void cautare(long long x,long long stanga){
	long long  st,dr,mij,j;
	st=stanga;
	dr=n;
	mij=(st+dr)/2;
	while (st<=dr)
	{
		if (a[mij]>x)
		{
			dr=mij-1;
			mij=(st+dr)/2;
			raspuns=mij;
		}
		else if (a[mij]<x)
		{
			st=mij+1;
			mij=(st+dr)/2;
			raspuns=mij;
		}
		else if (a[mij]=x) 
			{
				raspuns=mij;
				break;
		}
	}
}

int main(){
	freopen("zombie.in","r",stdin);
	freopen("zombie.out","w",stdout);
	scanf("%lld %lld %lld",&d,&n,&k);
	for (i=1; i<=n; ++i) scanf("%lld",&a[i]);
	i=1;
	while (i<=n)
	{
		t1=a[i]+d-1;
		cautare(t1,i);
		sum=(raspuns-i+1);
		if (a[n]<t1)
		{
			raspuns=n+1;
			sum=n-i;
		}
		if (sum>k)
		{
			suma=suma+k;
			i=raspuns+1;
		}
		else {
			suma++;
			i++;
		}
	}
	printf("%lld",suma);
	return(0);
}