Pagini recente » Cod sursa (job #2617097) | Cod sursa (job #322440) | Profil Khuten | Istoria paginii preoni-2008/clasament/runda-4/11-12 | Cod sursa (job #1008112)
#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);
}
void binSearch(long in, long sf, long su, long &newInd)
{
int k;
while (in <= sf)
{
k = (in + sf) / 2;
if (sume[k][0] + su <= S)
{
in = k + 1;
}
else
{
sf = k - 1;
}
}
k = (in + sf) / 2;
if (sume[k][0] + su > S)
{
k--;
}
if (sume[k][0] + su == S)
{
newInd = k;
}
}
void rezolvare()
{
float pos = (float) S/a[n-1];
if(pos > 6)
{
fout<<-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 = 0; j < n; j++)
{
for(long k = 0; 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);
for(long i = 0; i < ind; i++)
{
long indice = -1;
binSearch(0, ind-1, sume[i][0], indice);
if(indice != -1)
{
for(long j = 1; j <= 3; j++)
{
fout<<sume[i][j]<<' ';
}
for(long j = 1; j <= 3; j++)
{
fout<<sume[indice][j]<<' ';
}
break;
}
}
}
}
int main()
{
citire();
rezolvare();
return 0;
}