Cod sursa(job #1008155)

Utilizator PsychoAlexAlexandru Buicescu PsychoAlex Data 10 octombrie 2013 13:25:35
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#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;
}