Cod sursa(job #1008092)

Utilizator PsychoAlexAlexandru Buicescu PsychoAlex Data 10 octombrie 2013 10:43:44
Problema Loto Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 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 change(int &a, int &b)
{
    int aux = a;
    a = b;
    b = aux;
}

void poz(int li, int ls, int &k)
{
	int i1 = 1, j1 = 0;
	int 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(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++;
                    }
                }
            }

            Qsort(0, ind - 1);

            for(int i = 0; i < ind; i++)
            {
                int indice = -1;
                binSearch(0, ind-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;
}