Cod sursa(job #1692134)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 20 aprilie 2016 10:59:22
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
using namespace std;

ifstream in("test.in");
ofstream out("test.out");

int n,s,v[101]={},st[7]={},sum=0,sir[7];
bool unwritten=true;
int part(int *arr,int start,int end)
{
	int index=start,piv=arr[end],t;
	for(int i=start;i<=end;i++)
		if(arr[i]<=piv)
		{
			t=arr[i];
			arr[i]=arr[index];
			arr[index]=t;
			index++;
		}
		return index-1;
}
void srt(int *arr,int start,int end)
{
	int index;
	if(start<end)
	{
		index=part(arr,start,end);
		srt(arr,start,index-1);
		srt(arr,index+1,end);
	}
}
void write()
{ 
	for(int i=1;i<=6;i++)
		sir[i]=v[st[i]];
	srt(sir,1,6);
	for(int i=1;i<=6;i++)
		out<<sir[i]<<' ';
}
int Sum()
{
	int x=0;
	for(int i=1;i<=6;i++)
		x+=v[st[i]];
	return x;
}
void bsearch(int lvl)
{
	int start=1,end=n;
	int mid=(start+end)/2;
	st[lvl]=mid;
	while(start<=end)
	{
		mid=(start+end)/2;
		if(lvl<6)
			bsearch(lvl+1);
		sum=Sum();
		if(sum<s)
		{
			start=mid+1;
			st[lvl]=mid;
		}
		else if(sum>s)
		{
			end=mid-1;
			st[lvl]=mid;
		}
		else if(sum==s)
		{
			if(unwritten)
			{
				write();
				unwritten=false;
			}
			break;
		}
	}
}
void Read()
{
	in>>n>>s;
	for(int i=1;i<=n;i++)
		in>>v[i];
	srt(v,1,n);
}
int main()
{
	Read();
	bsearch(1);
	sum=Sum();
	if(sum==s&&unwritten)
	{
		write();
		unwritten=false;
	}
	if(unwritten)
		out<<-1;
	return 0;
}