Cod sursa(job #2211042)

Utilizator bisarenaBudai Istvan bisarena Data 9 iunie 2018 11:37:29
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

int x[100], v[6], N, S, ok=0, T, LSt=6;

ifstream f("loto.in");
ofstream g("loto.out");

int comp(const void* a, const void* b)
   {
     int* arg1 = (int*) a;
     int* arg2 = (int*) b;
     if( *arg1 < *arg2 ) return -1;
     else if( *arg1 == *arg2 ) return 0;
     else return 1;
   }

bool accept(int p)
{
    T = 0;
    for (int k=0; k<=p; ++k) T += x[v[p]];
    if (p<LSt-1 && T>=S) return false;
    return true;
}

void Back(int p)
{
    for (int j=0; j<N; j++)
    {
        v[p]=j;
        if (accept(p))
        {
            if (p<LSt-1) Back(p+1);
            else
            {
                T=0;
                for (int k=0; k<=p; ++k) T += x[v[k]];
                if (T==S)
                    {
                        for(int k1=0; k1<=LSt-1; ++k1) g<<x[v[k1]]<<" ";
                        ok=1;
                        exit(0);
                    }
            }
        }
    }
}

int main()
{
    f >> N >> S;
    for (int i=0; i<=N-1; ++i) f >> x[i];
    qsort(x, N, sizeof(int), comp);
    //exista S/6?
    if (S%6==0)
    {
        int s=S/6;
        //cautare, eventual binara
        for (int i=1; i<=N-1; ++i)
            if (s==x[i])
                {
                    for (int t=1; t<=6; ++t) g << s << " ";
                    f.close(); g.close();
                    return 0;
                }
    }
    Back(0);
    cout << '*';
    if(ok==0) g<<-1;
    f.close(); g.close();
    return 0;
}