Cod sursa(job #680694)

Utilizator crazzytudTudor Popa crazzytud Data 15 februarie 2012 20:29:50
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

int sum[1000001];
int v[101],u,S,n;

int cautbin(int suma)
{
    int i, pas=1<<19;
    for(i=0;pas!=0;pas>>=1)
        if(i+pas<u&&sum[i+pas]+suma<=S)
            i+=pas;
    if(sum[i]+suma==S)
        return i;
    else return -1;
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    int i,j,k,poz,poz1,poz2,poz3,poz4,poz5,poz6,sum1,sum2;
    scanf("%d%d",&n,&S);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);

    //Sume 3
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++)
            {
                sum[++u]=v[i]+v[j]+v[k];
            }
    //SORT
    sort(sum+1,sum+u+1);

    //CAUTBIN
    for(int z=1;z<=u;z++)
    {
        poz=cautbin(sum[z]);
        if(poz!=-1)
        {
            sum1=sum[poz];
            sum2=S-sum1;
            for(i=1;i<=n;i++)
                for(j=i;j<=n;j++)
                    for(k=j;k<=n;k++)
                    {
                        if(v[i]+v[j]+v[k]==sum1)
                        {
                            poz1=v[i];poz2=v[j];poz3=v[k];
                        }
                        if(v[i]+v[j]+v[k]==sum2)
                        {
                            poz4=v[i];poz5=v[j];poz6=v[k];
                        }

                    }



            printf("%d %d %d %d %d %d",poz1,poz2,poz3,poz4,poz5,poz6);
            return 0;
        }
    }
    printf("-1");
}