Cod sursa(job #680205)

Utilizator vladstoickvladstoick vladstoick Data 14 februarie 2012 12:16:07
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct sume
{
    int suma , first , second , third;
};
sume s[1000001];
int n , i , x , a[101];
bool comp(sume a , sume b)
{
    return a.suma>b.suma;
}
int cautbinar(int x)
{
    int i,pas=1<<19,nr=s[0].suma;
    for(i=0;pas!=0;pas>>=1)
    {
        if(i+pas<=nr && s[i+pas].suma<=x) i += pas;
    }
    if(s[i].suma!=x) return -1;
    return i;
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&n,&x);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int  i1 , i2;
    for(i=1;i<=n;i++)
    {
        for(i1=i;i1<=n;i1++)
        {
            for(i2=i1;i2<=n;i2++)
            {
                s[++s[0].suma].suma=a[i]+a[i1]+a[i2];
                s[s[0].suma].first=i;
                s[s[0].suma].second=i1;
                s[s[0].suma].third=i2;
            }
        }
    }
    int rez;
    sort(s+1,s+1+s[0].suma,comp);
    for(i=1;i<=s[0].suma;i++)
    {
        rez=cautbinar(x-s[i].suma);
        if(rez!=-1)
        {
            printf("%d %d %d ",s[i].first,s[i].second, s[i].third);
            printf("%d %d %d ",s[rez].first,s[rez].second, s[rez].third);
            return 0;
        }
    }
    printf("-1");
}