Cod sursa(job #1026240)

Utilizator george_stelianChichirim George george_stelian Data 11 noiembrie 2013 13:54:41
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>

using namespace std;

struct loto
{
    int s;
    char a;
    char b;
    char c;
};

loto aux,a[1000000];
int v[100],i,j,q,n,s,nr,b,y,x,st,dr,mid,sol;

void sort(int st,int dr)
{
    int i=st,j=dr;
    mid=a[(i+j)/2].s;
    do
    {
        while(a[i].s<mid) i++;
        while(a[j].s>mid) j--;
        if(i<=j)
        {
            aux=a[i];a[i]=a[j];a[j]=aux;
            i++;j--;
        }
    }while(i<=j);
    if(i<dr)sort(i,dr);
    if(j>st)sort(st,j);
}

int main()
{
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);
    scanf("%d%d",&n,&s);
    for(i=0;i<n;i++) scanf("%d",&v[i]);
    nr=-1;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            for(q=0;q<n;q++)
            {
                a[++nr].s=v[i]+v[j]+v[q];
                a[nr].a=i;
                a[nr].b=j;
                a[nr].c=q;
            }
    sort(0,nr);
    b=-1;
    y=-1;
    for(i=0;i<=nr;i++)
    {
        sol=-1;
        st=0;dr=nr;
        x=s-a[i].s;
        while(st<=dr)
        {
            if(a[(st+dr)/2].s==x)
            {
                sol=(st+dr)/2;
                break;
            }
            if(a[(st+dr)/2].s<x) dr=(st+dr)/2-1;
            else st=(st+dr)/2+1;
        }
        if(sol>-1)
        {
            b=i;
            y=sol;
            break;
        }
    }
    if(b>-1) printf("%d %d %d %d %d %d",v[a[b].a],v[a[b].b],v[a[b].c],v[a[y].a],v[a[y].b],v[a[y].c]);
    else printf("-1");
    fclose(stdin);fclose(stdout);
    return 0;
}