Cod sursa(job #392076)

Utilizator pykhNeagoe Alexandru pykh Data 6 februarie 2010 18:22:54
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

const char in[]="loto.in";
const char out[]="loto.out";
const int N=105;
int s[3000000], v[N], S, n;
struct cmp{
	bool operator()(const long &a, const long &b)
	{
		return a<b;
	}
	};



void nr(int numar)
{
	int i, j, k;
	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
			for(k=1;k<=n;++k)
				if(v[i]+v[j]+v[k]==numar){
					printf("%d %d %d ", v[i], v[j], v[k]);
				return;
				}
}

int main()
	{
		freopen(in,"r",stdin);
		freopen(out,"w",stdout);
		scanf("%d %d", &n, &S);
		int i, j, k;
		for(i=1;i<=n;++i)
			scanf("%d", &v[i]);
		for(i=1;i<=n;++i)
			for(j=1;j<=n;++j)
				for(k=1;k<=n;++k)
					s[++v[0]]=v[i]+v[j]+v[k];
		sort(s+1, s+v[0]+1, cmp());
		int hi, lo, mid;
			for(i=1;i<=v[0];++i)
			{
				for(hi=v[0], lo=1; lo<=hi;)
				{
					mid=lo+(hi-lo)/2;
					if(s[mid] == S-s[i]){
						nr(s[mid]), nr(s[i]);return 0;}
					else {
						if(s[mid]<S-s[i])lo=mid+1;
						else hi=mid-1;
					}
				}
			}
		printf("-1\n");
	return 0;
}