Cod sursa(job #493503)

Utilizator nbibestNeagu Bogdan Ioan nbibest Data 18 octombrie 2010 16:51:52
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

int n,s,i,j,v[101],vv[101],m[20000000][4],k,aux[4],sum[2000000],ok,mij;


int bin(int x)
{
    int s,d;

    s=1;d=k;
    mij=(s+d)/2;

    while((x!=sum[mij])&&(d-s>0))
    {
        if (sum[mij]>x)
        {
            d=mij-1;
        }
        else s=mij+1;
        mij=(s+d)/2;

    }

    if (x==sum[mij])
    {
        ok=1;
    }

}

int back(int p)
{

    int i;
    if (p==4)
    {
        k++;
        int j,ss;
        ss=0;
        for (j=1;j<=3;j++)
        {
            m[k][j]=v[vv[j]];
            ss=ss+v[vv[j]];
        }
        m[k][0]=ss;
        sum[k]=ss;
    }
    else
    {
        for (i=1;i<=n;i++)
        {
            vv[p]=i;
            back(p+1);
        }
    }

}



int main()
{

    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);

    scanf("%d%d",&n,&s);

    for (i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
    }

    back(1);


    /*for (i=1;i<=k;i++)
    {
        int gata=1;
        for (j=i;j<=k-1;j++)
        {
            if (m[j][0]>m[j+1][0])
            {
                int z;
                for (z=0;z<=3;z++)
                {
                aux[z]=m[j][z];
                m[j][z]=m[j+1][z];
                m[j+1][z]=aux[z];
                gata=0;
                }
            }
        }
        if (gata==1) i=k+1;
    }
*/
    //qsort(sum);
    sort(sum,sum+k);



    //for (i=1;i<=k;i++)
    //printf("%d\n",sum[i]);

    ok=0;
    //printf("%d\n",k);
    for (i=1;i<=k;i++)
    {
        int c=0;
        c=s-m[i][0];
        bin(c);
        //printf("%d ",m[i][0]);

        if (ok==1)
        {
            int a=0,b=0,jj;

            for (jj=1;jj<=k;jj++)
            {
                if ((m[i][0]==m[jj][0])&&(a==0)) a=jj;
                if ((c==m[jj][0])&&(b==0)) b=jj;

            }

            for (j=1;j<=3;j++)
            printf("%d ",m[a][j]);

            for (j=1;j<=3;j++)
            printf("%d ",m[b][j]);

            //printf("\n%d",mij);

            i=1000000;

        }
    }


    if (ok==0)
    printf("-1");

    return 0;
}