Pagini recente » Cod sursa (job #3285558) | Borderou de evaluare (job #888945) | Cod sursa (job #44509) | Cod sursa (job #2255088) | Cod sursa (job #1011527)
#include <iostream>
#include <fstream>
#include <algorithm>
std::ifstream fin("loto.in");
std::ofstream fout("loto.out");
struct sssum
{
long sum, a, b, c;
} sume[10000001];
long n, S, a[1001], myS, nrUsed, sol[6], ind;
void change(long &a, long &b)
{
long aux = a;
a = b;
b = aux;
}
inline bool cmp(sssum q, sssum w)
{
if(q.sum <= w.sum)
{
return true;
}
return false;
}
void poz(long li, long ls, long &k)
{
int i1 = 1, j1 = 0;
long i = li, j = ls;
while(i < j)
{
if(sume[i].sum > sume[j].sum)
{
change(sume[i].sum, sume[j].sum);
change(sume[i].a, sume[j].a);
change(sume[i].b, sume[j].b);
change(sume[i].c, sume[j].c);
//daca am interschimbat 2 valori, atunci schimbam directia din care venim
//daca am inceput din stanga, atunci trecem in dreapta
if(i1 == 1)
{
i1 = 0;
j1 = -1;
}
else
//daca am inceput din dreapta, atunci trecem in stanga
{
i1 = 1;
j1 = 0;
}
}
i += i1;
j += j1;
}
k = i;
}
void Qsort(long li, long ls)
{
long k;//k e modificat in poz(int, int, int&)
if(li < ls)
{
poz(li, ls, k);
Qsort(li, k - 1);
Qsort(k + 1, ls);
}
}
void citire()
{
fin>>n>>S;
for(long i = 0; i < n; i++)
{
fin>>a[i];
}
// Qsort(0, n-1);
}
long binSearch(long in, long sf, long su)
{
long m;
while(in <= sf)
{
m = (in + sf) / 2;
if(sume[m].sum + su < S)
{
in = m+1;
}
else
if(sume[m].sum + su > S)
{
sf = m-1;
}
else
{
return m;
}
}
return -1;
}
void rezolvare()
{
float pos = (float) S/a[n-1];
// if(pos > 6)
// {
// std::cout<<"111: "<<-1<<'\n';
// }
// else
// if(S % a[n-1] == 0 && S / a[n-1] == 6)
// {
// for(long i = 0; i < 6; i++)
// {
// fout<<a[n-1]<<' ';
// }
// fout<<'\n';
// }
// else
{
for(long i = 0; i < n; i++)
{
for(long j = i; j < n; j++)
{
for(long k = j; k < n; k++)
{
sume[ind].sum = a[i] + a[j] + a[k];
sume[ind].a = a[i];
sume[ind].b = a[j];
sume[ind].c = a[k];
if(sume[ind].sum * 2 == S)
{
fout<<a[i]<<' '<<a[j]<<' '<<a[k]<<' '<<a[i]<<' '<<a[j]<<' '<<a[k]<<'\n';
return;
}
ind++;
}
}
}
///Qsort(0, ind - 1);
std::sort(sume, sume+ind, cmp);
// for(int i = 0; i < ind; i++)
// {
// std::cout<<sume[i].sum<<' ';
// }
bool found = false;
// long p1 = 0, p2 = ind - 1;
//
// while(p1 <= p2)
// {
// if(sume[p1][0] + sume[p2][0] < S)
// {
// p1++;
// }
// else
// if(sume[p1][0] + sume[p2][0] > S)
// {
// p2--;
// }
// else
// {
// for(long j = 1; j <= 3; j++)
// {
// fout<<sume[p1][j]<<' ';
// }
// for(long j = 1; j <= 3; j++)
// {
// fout<<sume[p2][j]<<' ';
// }
// return;
// }
// }
for(long i = 0; i < ind; i++)
{
long indice = binSearch(0, ind-1, sume[i].sum);
if(indice != -1)/// && sume[i][0] < S)
{
// for(long j = 1; j <= 3; j++)
{
fout<<sume[i].a<<' '<<sume[i].b<<' '<<sume[i].c<<' ';
}
// for(long j = 1; j <= 3; j++)
{
fout<<sume[indice].a<<' '<<sume[indice].b<<' '<<sume[indice].c<<' ';
}
return;
}
}
if(!found)
{
fout<<-1<<'\n';
}
}
}
int main()
{
citire();
rezolvare();
return 0;
}