Cod sursa(job #805002)

Utilizator assa98Andrei Stanciu assa98 Data 30 octombrie 2012 20:00:54
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <stdio.h>
#include<algorithm>
using namespace std;

int v[110];
int n;

struct sp
{
    int s;
    int a,b;
} sume[1000010];

int cs;

int S;

bool cmp(sp a,sp b)
{
    return a.s<b.s;
}


int cauta(int s,int f,int x)
{
    if(s>f)
        return -1;
    int mij=(s+f)/2;
    if(x==sume[mij].s)
        return mij;
    if(x>sume[mij].s)
        return cauta(mij+1,f,x);
    if(x<sume[mij].s)
        return cauta(s,mij-1,x);
}

int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&n,&S);
    for(int i=1; i<=n; i++)
        scanf("%d",&v[i]);
    //sort(v+1,v+n+1);
    int j,k;
    for(int i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            for(k=1; k<=n; k++)
            {
                sume[++cs].s=v[i]+v[j]+v[k];
                sume[cs].a=v[i];
                sume[cs].b=v[j];
            }
    sort(sume+1,sume+cs+1,cmp);
    int sm;

    for(int i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            for(k=1; k<=n; k++)
            {
                sm=cauta(1,cs,S-v[i]-v[j]-v[k]);
                if(sm!=-1)
                {
                    printf("%d %d %d %d %d %d\n",v[i],v[j],v[k],
                           sume[sm].a, sume[sm].b, sume[sm].s - sume[sm].a - sume[sm].b);
                    return 0;
                }
            }
    printf("-1");
    return 0;
}