Cod sursa(job #880223)

Utilizator Detrol2kGuianu Leon Detrol2k Data 16 februarie 2013 15:07:10
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

int size = 0;

struct sum
{
	int x, y, z, s;
}v[2000000];

bool cmp(sum a, sum b)
{
	return a.s < b.s;
}

int binary_search(int p)
{
	int left = 1, right = size, mid;
	
	while(left <= right)
	{
		mid = (left+right)/2;
		if(v[mid].s == p)
			return mid;
		if(p < v[mid].s)
			right = mid-1;
		else
			left = mid+1;
	}
	return 0;
}

int main()
{
	ifstream fin("loto.in");
	ofstream fout("loto.out");
	
	int n, ts, i, j, k, t, aux[200];
		
	//Read
	fin>>n>>ts;
	for(i=1; i<=n; i++)
		fin>>aux[i];


	//Compute
	for(i=1; i<=n; i++)
		for(j=i; j<=n; j++)
			for(k=j; k<=n; k++)
			{
				size++;
				v[size].x = aux[i];
				v[size].y = aux[j];
				v[size].z = aux[k];
				v[size].s = aux[i]+aux[j]+aux[k];
			}
	sort(v+1,v+n+1,cmp);
	for(i=1; i<=size; i++)
	{
		if( (t=binary_search(ts-v[i].s)) != 0)
		{
			fout<<v[i].x<<" "<<v[i].y<<" "<<v[i].z<<" "<<v[t].x<<" "<<v[t].y<<" "<<v[t].z;
			return 0;
		}	
	}
	fout<<"-1";
}