Cod sursa(job #269699)

Utilizator ooctavTuchila Octavian ooctav Data 3 martie 2009 11:37:36
Problema Zebughil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
// zebughil.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>

int e[18];
bool f[18];
int comparare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int cautare(int j,int n,int g)
{
	int st=j+1,dr=n,mij,rez=0;
	while(st<=dr)
	{
		mij=st+(dr-st)/2;
		if(e[mij]==g-e[j])
		{
			if(!f[j])
				return mij;
		}
		else if(e[mij]<g-e[j])
		{
			if(!f[j])
				rez=mij;
			st=mij+1;
		}
		else
			dr=mij-1;
	}
	return rez;
}

int main()
{
	freopen("zebughil.in","r",stdin);
	freopen("zebughil.out","w",stdout);
	int n,i,g,j,nrcamioane,a;
	for(i=1;i<=3;i++)
	{
		scanf("%d %d\n",&n,&g);
		nrcamioane=n;
		for(j=1;j<=n;j++)
			scanf("%d",&e[j]);
		qsort(e,n+1,sizeof(e[1]),comparare);
		for(j=1;j<=n;j++)
		{
			if(f[j])
				continue;
			a=cautare(j,n,g);
			if(a)
			{	f[j]=true;
				f[a]=true;
				nrcamioane--;
			}
			else 
				break;
		}
		for(j=1;j<18;j++)
		{
			e[j]=0;
			f[j]=false;
		}
		printf("%d\n",nrcamioane);
	}


	return 0;
}