Cod sursa(job #981446)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 7 august 2013 09:56:39
Problema Loto Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=110;
const int MAXB=200000;
int n,s,nrb;
int v[MAXN];
struct loto
{
	int s,i,j,k;
};
loto b[MAXB];
void read()
{
	FILE *fin=fopen("loto.in","r");
	fscanf(fin,"%d%d",&n,&s);
	for (int i=1; i<=n; ++i)
		fscanf(fin,"%d",&v[i]);
	fclose(fin);
}
int binary_search(int low, int high, int value)
{
	int mid;
	while (low<=high)
	{
		mid=(low+high)/2;
		if (b[mid].s==value)
			return mid;
		else if (value<b[mid].s)
			high=mid-1;
		else if (value>b[mid].s)
			low=mid+1;
	}
	return 0;
}
bool cmp(loto a, loto b)
{
	return a.s<b.s;
}
void solve()
{
	FILE *fout=fopen("loto.out","w");

	int i,j,k;
	for (i=1; i<=n; ++i)
	{
		for (j=1; j<=n; ++j)
		{
			for (k=1; k<=n; ++k)
			{
				++nrb;
				b[nrb].s=v[i]+v[j]+v[k];
				b[nrb].i=i;
				b[nrb].j=j;
				b[nrb].k=k;
			}
		}
	}
	sort(b+1,b+nrb+1,cmp);
	i=j=0;
	for (i=1; i<=nrb; ++i)
	{
		j=binary_search(1,nrb,s-b[i].s);
		if (j)
		{
			fprintf(fout,"%d %d %d %d %d %d\n",v[b[i].i],v[b[i].j],v[b[i].k],v[b[j].i],v[b[j].j],v[b[j].k]);
			fclose(fout);
			return;
		}
	}
	fprintf(fout,"-1\n");
	fclose(fout);
}
int main()
{
	read();
	solve();
	return 0;
}