Cod sursa(job #981465)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 7 august 2013 11:22:57
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<fstream>
#include<algorithm>

using namespace std;

#define max_sum 1000010

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

int n , s , i , j , k , vf;

struct suma{
	int i , j , k  , sum;
}Sum[max_sum];

int V[200];
int Sol[20];

void read(){
	
	f>>n>>s;
	
	for(int i = 1 ; i <= n ; i++)
		f>>V[i];
	
}

int search( int x ){
	
	int st = 1 , dr = vf;
	int mid = (st+dr)/2;
	
	while( st <= dr ){
		
		if(Sum[mid].sum == x)
			return mid;
		if(Sum[mid].sum < x)
			st = mid+1;
		else
			dr = mid-1;
		
		mid = (st+dr)/2;
		
	}
	return -1;
}

void print( int a , int b ){
	Sol[1] = V[Sum[a].i]; Sol[2] = V[Sum[a].j]; Sol[3] = V[Sum[a].k];
	Sol[4] = V[Sum[b].i]; Sol[5] = V[Sum[b].j]; Sol[6] = V[Sum[b].k];
	
	sort(Sol+1 , Sol+7);
	
	for( int i = 1 ; i <= 6 ; i++ )
		g<<Sol[i]<<" ";
	
}

void solve(){
	
	int x;
	
	for( int i = 1 ; i <= vf ; i++ ){
		
		x = search(s - Sum[i].sum);
		
		if( x != -1 ){
			print(i , x);
			return;
		}
		
	}
	
	g<<"-1\n";
}

int cmp( suma a , suma b ){
	return a.sum < b.sum;
}

int main(){
	
	read();
	
	for(i = 1 ; i <= n ; i++)
		for(j = i ; j <= n ; j++)
			for(k = j ; k<= n ; k++){
				
				if( V[i]+V[j]+V[k] > s )	continue;
				
				Sum[++vf].i = i; Sum[vf].j = j; Sum[vf].k = k; Sum[vf].sum = V[i]+V[j]+V[k];
				
			}
	
	sort(Sum+1 , Sum+vf+1 , cmp);
	
	solve();
	
	return 0;
}