Cod sursa(job #1022451)

Utilizator BuseSorinFMI Buse Sorin-Marian BuseSorin Data 5 noiembrie 2013 14:32:47
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

struct suma{
	int s, i, j, k;
};

int cmp(const void* s1, const void* s2){
	if ((*(suma*)s1).s > (*(suma*)s2).s){
		return 1;
	}
	return -1;
}
int binSearch(suma S[], int stanga, int dreapta, int x){
	while (stanga <= dreapta){
		int mij = (dreapta + stanga) / 2;
		if (x == S[mij].s){
			return mij;
		}
		else{
			if (x < S[mij].s){
				dreapta = mij - 1;
			}
			else{
				stanga = mij + 1;
			}
		}
	}
	return -1;
}
int main(){

	ifstream f("loto.in");
	ofstream o("loto.out");

	int n = 0, s22 = 0;
	int V[100];
	suma S[1000000];
	int indexS = 0;
	f >> n >> s22;
	for (int i = 0; i < n; i++)
	{
		f >> V[i];
	}
	for (int i = 0; i < n; i++){
		for (int j = i; j < n; j++){
			for (int k = j; k < n; k++){
				int s1 = V[i] + V[j] + V[k];
				if (s1 <= s22){
					suma c;
					c.i = V[i];
					c.j = V[j];
					c.k = V[k];
					c.s = s1;
					S[indexS++] = c;
				}
			}
		}
	}
	qsort(S, indexS, sizeof(suma), cmp);
	bool g = false;
	for (int i = 0; i < indexS; i++){
		int comp = s22 - S[i].s;
		int m = binSearch(S, 0, indexS, comp);
		if (m != -1){
			o << S[i].i << " " << S[i].j << " " << S[i].k << " " << S[m].i << " " << S[m].j << " " << S[m].k << '\n';
			g = true;
			break;
		}
	}
	if (g == false)
		o << -1;
	return 0;
}