Cod sursa(job #486018)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 20 septembrie 2010 12:35:55
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<fstream>
#include<iostream>
#include<vector>
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+k;
	}
	uint32 sum,i,j,k;
};

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;
	
	fin>>n>>S;
	//cout<<n<<" "<<S<<endl;
	for(int i=0; i<n; ++i)
	{
		fin>>x;
		v.push_back(x);
	}
	/*for(int i=0; i<n; ++i)
	{
		cout<<v[i]<<" ";
	}
	cout<<endl;*/
	
	for(int i=0; i<n; ++i)
	{
		for(int j=i; j<n; ++j)
		{
			for(int k=j; k<n; ++k)
			{
				sums.push_back(Parts(v[i],v[j],v[k]));
			}
		}
	}

	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].k<<" "<<sums[index].i<<" "<<sums[index].j<<" "<<sums[index].k<<endl;
			return 0;
		}
	}
	fout<<-1<<endl;
	
	fin.close();
	fout.close();
	return 0;
}