Mai intai trebuie sa te autentifici.
Cod sursa(job #1008087)
Utilizator | Data | 10 octombrie 2013 10:40:06 | |
---|---|---|---|
Problema | Loto | Scor | 5 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.79 kb |
#include <iostream>
#include <fstream>
std::ifstream fin("loto.in");
std::ofstream fout("loto.out");
int n, S, a[101], myS, nrUsed, sol[6], sume[1000001][4], ind;
void poz(int li, int ls, int &k)
{
int i1 = 1, j1 = 0;
int i = li, j = ls;
while(i < j)
{
if(a[i] > a[j])
{
int aux = a[i];
a[i] = a[j];
a[j] = aux;
//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(int li, int ls)
{
int 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(int i = 0; i < n; i++)
{
fin>>a[i];
}
// Qsort(0, n-1);
}
void binSearch(int in, int sf, int su, int &newInd)
{
if(in < sf)
{
int k = (in + sf) / 2;
if(sume[k][0] + su == S)
{
newInd = k;
}
else
if(sume[k][0] + su > S)
{
binSearch(in, k-1, su, newInd);
}
else
{
binSearch(k+1, sf, su, newInd);
}
}
}
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(int i = 0; i < 6; i++)
{
fout<<a[n-1]<<' ';
}
fout<<'\n';
}
else
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
for(int 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++;
}
}
}
for(int i = 0; i < ind; i++)
{
int indice = -1;
binSearch(0, n-1, sume[i][0], indice);
if(indice != -1)
{
for(int j = 1; j <= 3; j++)
{
fout<<sume[i][j]<<' ';
}
for(int j = 1; j <= 3; j++)
{
fout<<sume[indice][j]<<' ';
}
break;
}
}
}
}
int main()
{
citire();
rezolvare();
return 0;
}