Cod sursa(job #813734)

Utilizator bogdan93Grigorescu Bogdan bogdan93 Data 15 noiembrie 2012 19:18:03
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <cstdlib>
#include <cstdio>
#include <ctime>


long long s;
int n,v[101];

void swap(int *a,int *b)
{
     int aux = *a;
     *a = *b;
     *b = aux;
}
int caut_piv(int v[],int l,int r)
{
    int m = r;

    l--;


    while ( l<r && v[++l]<v[m] );
    while ( l<r && v[--r]>v[m] );

    if ( l<r )
             swap(&v[l],&v[r]);
    swap (&v[l],&v[r]);
    return l;
}


void qsort(int v[],int l,int r)
{
     if ( l>=r )        return;
     int m = caut_piv(v,l,r);
     qsort(v,l,m-1);
     qsort(v,m+1,r);
}


int main()
{
    FILE *f,*g;
    f = fopen("loto.in","r");
    g = fopen("loto.out","w");

    fscanf(f,"%d %lld",&n,&s);
    for (int i = 1 ; i <= n; i++)
        fscanf(f,"%d",&v[i]);

    fclose(f);



    qsort(v,1,n);

    long long a,b,c,d,e,af;
    int ok = 0;

    for ( a = 1; a <= n && 5*v[a]<=s; a++)
        for ( b = a; b <= n && 4*v[b]+v[a]<=s; b++)
            for ( c = b; c <= n && 3*v[c]+v[b]+v[a]<=s; c++)
                for ( d = c; d <= n && 2*v[d]+v[c]+v[b]+v[a]<=s; d++)
                    for ( e = d; e <= n  ; e++)
                        for ( af = e; af <= n ; af++)
                        if (v[af]+v[a]+v[b]+v[c]+v[d]+v[e] == s)
                        {
                                                         ok = 1;
                                                         goto exit;
                        }

        exit:
         if ( ok )         fprintf(g,"%d %d %d %d %d %d\n",v[a],v[b],v[c],v[d],v[e],v[af]);
            else fprintf(g,"-1\n");

    fclose(g);
    return 0;
}