Pagini recente » Cod sursa (job #2326175) | Cod sursa (job #937467) | Cod sursa (job #2740315) | Cod sursa (job #294971) | Cod sursa (job #1008155)
#include <iostream>
#include <fstream>
std::ifstream fin("loto.in");
std::ofstream fout("loto.out");
long n, S, a[1001], myS, nrUsed, sol[6], sume[10000001][4], ind;
void change(long &a, long &b)
{
long aux = a;
a = b;
b = aux;
}
void poz(long li, long ls, long &k)
{
int i1 = 1, j1 = 0;
long i = li, j = ls;
while(i < j)
{
if(sume[i][0] > sume[j][0])
{
change(sume[i][0], sume[j][0]);
change(sume[i][1], sume[j][1]);
change(sume[i][2], sume[j][2]);
change(sume[i][3], sume[j][3]);
//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][0] + su <= S)
{
in = m+1;
}
else
{
sf = m-1;
}
}
m = (in + sf) / 2;
if(sume[m][0] + su > S)
{
m--;
}
if(S == su + sume[m][0])
{
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][0] = a[i] + a[j] + a[k];
sume[ind][1] = a[i];
sume[ind][2] = a[j];
sume[ind][3] = a[k];
ind++;
}
}
}
Qsort(0, ind - 1);
bool found = false;
for(long i = 0; i < ind; ++i)
{
long indice = binSearch(0, ind-1, sume[i][0]);
if(indice != -1 && sume[i][0] < S)
{
for(long j = 1; j <= 3; j++)
{
fout<<sume[i][j]<<' ';
}
for(long j = 1; j <= 3; j++)
{
fout<<sume[indice][j]<<' ';
}
return;
}
}
if(!found)
{
fout<<-1<<'\n';
}
}
}
int main()
{
citire();
rezolvare();
return 0;
}