Cod sursa(job #895479)

Utilizator gaby1995Calin Gabriel Iulian gaby1995 Data 27 februarie 2013 11:33:52
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include<iostream>
#include<fstream>
using namespace std;
unsigned short n;
unsigned long int s;
unsigned long long v[101] , x[101] , S, sr ,st[101],k,ess;
ofstream g("loto.out");
void qSort(unsigned long long x[],short st,short dr)
{
   int temp,min,max,mijl;

   mijl = x[st+(dr-st)/2];
   min = st; max = dr;
   do
   {
        while(x[min] < mijl) min++;
        while(x[max] > mijl) max--;
        if(min <= max)
        {
            temp = x[min];
            x[min++] = x[max];
            x[max--] = temp;
        }
    }while(min <= max);

    if(st < max) qSort(x,st,max);
    if(dr > min) qSort(x,min,dr);
}
void bagainvect()
{
    ess=0;
    for (int i=1;i<=n;i++)
        ess+=st[i];

    if (ess==sr)
     for (int i=4;i<=6;i++)
         x[i]=st[i-3];
}
void back (int k)
{
    int i;
    for (i=1;i<=n;i++)
    {
        st[k]=v[i];
            if (k==3)
             {
             bagainvect();
             break;
             }
        else
            back(k+1);
    }
}
void resolve ()
{
    int i;
    // sortez
    qSort(v,1,n);

    /*for (i=1;i<=n;i++)
         cout<<" "<<v[i];
    cout<<"--"<<v[n]*6<<"&&&"<<s; */

    if (v[n]*6<s)
        g<<-1;
    else
    {
        for (i=1;i<=n;i++)
            x[i]=v[i];
        back(1);
        for (i=1;i<=6;i++)
             g<<x[i]<<" ";
    }
        // trebuie sa formez 3 numere formate din suma sr cu metoda backtracking


}
void readngo()
{
    unsigned short i;
    ifstream f("loto.in");
    f>>n;
    f>>s;
    for (i=1;i<=n;i++)
        {
            f>>v[i];
            S+=v[i];
        }
        //cout<<s<<"*"<<S;
    sr=s-S;
    if (sr<0)
        g<<-1;
    else
        resolve();

    f.close();
}
int main ()
{
    readngo ();
    g.close();
}