Cod sursa(job #486048)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 20 septembrie 2010 13:12:05
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef unsigned int uint32;

struct Parts
{
	Parts()
	{}
	Parts(const uint32 ii, const uint32 jj, const uint32 kk) : i(ii), j(jj)//, k(kk)
	{
		sum=i+j+kk;
	}
	uint32 sum,i,j;
};

struct Comparator
{
	inline bool operator() (const uint32 a, const uint32 b) const
	{
		return a<b;
	}
};

struct ComparatorSums
{
	inline bool operator() (const Parts& a, const Parts& b) const
	{
		return a.sum<b.sum;
	}
};

unsigned int BinSearch(const vector<Parts>& v, const unsigned int val)
{
	unsigned int step,i;
	for(step=1; step<v.size(); step<<=1) ;
	for(i=0; step; step>>=1)
		if(i+step<v.size() && v[i+step].sum<=val)
			i+=step;
	return i;
}

int main()
{
	int n,x;
	long long S;
	fstream fin("loto.in", fstream::in);
	fstream fout("loto.out", fstream::out);
	vector<uint32> v;
	vector<Parts> sums;
	//Comparator com;
	ComparatorSums coms;
	
	fin>>n>>S;
	//cout<<n<<" "<<S<<endl;
	for(int i=0; i<n; ++i)
	{
		fin>>x;
		v.push_back(x);
	}
	fin.close();
	//sort(v.begin(), v.end(), com);
	
	/*for(int i=0; i<n; ++i)
	{
		cout<<v[i]<<" ";
	}
	cout<<endl;*/
	
	for(int i=0; i<n; ++i)
	{
		for(int j=0; j<n; ++j)
		{
			for(int k=0; k<n; ++k)
			{
				sums.push_back(Parts(v[i],v[j],v[k]));
			}
		}
	}

	sort(sums.begin(), sums.end(), coms);
	
	/*for(int i=0; i<(int)sums.size(); ++i)
	{
		cout<<sums[i].sum<<" ";
	}
	cout<<endl;*/

	for(int i=0; i<(int)sums.size(); ++i)
	{
		//cout<<sums[i].sum<<" ";
		const unsigned int index=BinSearch(sums,S-sums[i].sum);
		if(index<sums.size() && sums[index].sum==S-sums[i].sum)
		{
			fout<<sums[i].i<<" "<<sums[i].j<<" "<<sums[i].sum-(sums[i].i+sums[i].j)<<" "<<sums[index].i<<" "<<sums[index].j<<" "<<
			sums[index].sum-(sums[index].i+sums[index].j)<<endl;
			
			fout.close();
			return 0;
		}
	}
	fout<<-1<<endl;

	fout.close();
	return 0;
}