Cod sursa(job #40739)

Utilizator DastasIonescu Vlad Dastas Data 27 martie 2007 18:17:51
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <stdio.h>

FILE *in = fopen("loto.in","r"), *out = fopen("loto.out","w");

int n, s;
int a[100];

struct sume
{
    int val;
    int nr1, nr2, nr3;
};

sume *v = new sume[1000000];

int poz(int p, int u)
{
	int s=p, d=u;
	sume x=v[p];
	while ( s < d )
	{
		while ( v[d].val >= x.val && s < d )
			--d;
		v[s] = v[d];
		while ( v[s].val <= x.val && s < d )
			++s;
		v[d] = v[s];
	}
	v[s] = x;
	return s;
}

void qs(int p, int u)
{
	int m = poz(p, u);
	if ( p < m )
		qs(p, m-1);
	if ( m < u )
		qs(m+1, u);
}

int main()
{
    fscanf(in, "%d %d", &n, &s);


    for ( int i = 0; i < n; ++i )
        fscanf(in, "%d", &a[i]);

    int p = 0;
    for ( int i = 0; i < n; ++i )
        for ( int j = i; j < n; ++j )
            for ( int k = i; k < n; ++k )
            {
                v[p].val = a[i] + a[j] + a[k];
                v[p].nr1 = a[i];
                v[p].nr2 = a[j];
                v[p].nr3 = a[k];
                ++p;
            }

    qs(0, p-1);

    int sta = 0, sto = p-1;

    while ( sta <= sto )
    {
        int q = v[sto].val + v[sta].val;
        if ( q == s )
        {
            fprintf(out, "%d %d %d %d %d %d\n", v[sto].nr1, v[sto].nr2, v[sto].nr3,
                v[sta].nr1, v[sta].nr2, v[sta].nr3);

            return 0;
        }
        else if ( q < s )
            ++sta;
        else
            --sto;
    }

    fprintf(out, "%d\n", -1);

    return 0;
}