Cod sursa(job #813331)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 15 noiembrie 2012 11:13:39
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define Nmax 101

int V[Nmax], A[Nmax * Nmax *Nmax], N, M, S;
vector<int> sol;

int main() {
	
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	
	int i, j, k, st, dr, mij, sum;
	
	scanf("%d %d",&N,&S);
	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++) 
				if(V[i] + V[j] + V[k] < S) 
					A[++M] = V[i] + V[j] + V[k];
	sort(A+1,A+M+1);
	
	for(i=1; i<=N; i++)
		for(j=1; j<=N; j++)
			for(k=1; k<=N; k++) {
				sum = V[i] + V[j] + V[k];
				st = 1; dr = M;
				while(st<=dr) {
					mij=(st+dr)/2;
					if(A[mij] == S - sum) {
						sol.push_back(V[i]);
						sol.push_back(V[j]);
						sol.push_back(V[k]);
						i = j = k = N+1;
						S-=sum;
					}
					if(A[mij] < S - sum)
						st = mij + 1;
					else
						dr = mij - 1;
				}
			}
			
	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] == S) {
					printf("%d %d %d ",V[i],V[j],V[k]);
					for(vector<int>:: iterator it=sol.begin(); it!=sol.end(); ++it)
						printf("%d ",*it);
					return 0;
				}
				
	printf("-1\n");
	
	return 0;
}