Cod sursa(job #49124)

Utilizator the_dragon_of_rockTzogorean Alex the_dragon_of_rock Data 5 aprilie 2007 13:04:00
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<fstream>
using namespace std;
int a[200],n,s,suma[500],m,a1[500],a2[500],a3[500],sb,x[5];

void qsort(int st, int dr)
{
    if (st<dr)
        {
            int i=st,j=dr,d=0,aux;
            while(i<j)
                {
                if (suma[i]>suma[j])
                    {
                        aux=suma[i];
                        suma[i]=suma[j];
                        suma[j]=aux;
                        aux=a1[i];
                        a1[i]=a1[j];
                        a1[j]=aux;
                        aux=a2[i];
                        a2[i]=a2[j];
                        a2[j]=aux;
                        aux=a3[i];
                        a3[i]=a3[j];
                        a3[j]=aux;
                        d=1-d;
                    }
                i+=d;
                j-=1-d;
                }
            qsort(st,i-1);
            qsort(i+1,dr);
        }
}

void back(int k)
{
    int i;
    for (i=1;i<=n;i++)
        {
            x[k]=i;
            sb+=x[k];
            if (k==3)
                {
                    suma[++m]=sb;
                    a1[m]=x[1];
                    a2[m]=x[2];
                    a3[m]=x[3];
                }
            else
                back(k+1);
            sb-=x[k];
        }
}

int poz(int st, int dr, int t)
{
    int m=(st+dr)/2;
    if (suma[m]+suma[t]==s && m!=t)   return m;
    if (st>dr)   return -1000;
    if (suma[m]+suma[t]>s)
        return poz(st,m-1,t);
    else
        return poz(m+1,dr,t);
}

int main()
{
    ifstream in("loto.in");
    in>>n>>s;
    int i,gata=0,k;
    for (i=1;i<=n;i++)
        in>>a[i];
    in.close();
    
    back(1);
    qsort(1,m);
    
    ofstream out("loto.out");
    /*for (i=1;i<m && !gata;i++)
        {
            k=poz(i+1,m,suma[i]);
            if (k>0)
                {
                    out<<a1[i]<<" "<<a2[i]<<" "<<a3[i]<<" ";
                    out<<a1[k]<<" "<<a2[k]<<" "<<a3[k];
                    gata=1;
                }
        }
    if (gata==0)
        out<<-1;*/
    if (s>suma[m]+suma[m-1])
        out<<-1;
    else
    {
    k=poz(1,m,m/2);
    i=m/2;
    out<<a1[i]<<" "<<a2[i]<<" "<<a3[i]<<" ";
    out<<a1[k]<<" "<<a2[k]<<" "<<a3[k];
    }
    return 0;
}