Pagini recente » Cod sursa (job #1780066) | Cod sursa (job #1938882) | Cod sursa (job #256420) | Cod sursa (job #622831) | Cod sursa (job #1692002)
#include <fstream>
using namespace std;
ifstream in("loto.in");
ofstream out("loto.out");
int n,s,v[101]={},st[7]={},sum=0;
bool unwritten=true;
void write()
{
for(int i=1;i<=6;i++)
out<<v[st[i]]<<' ';
}
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);
}
}
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;
}