Cod sursa(job #680200)

Utilizator crazzytudTudor Popa crazzytud Data 14 februarie 2012 12:09:25
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct loto{
    int sum,i,j,k;
 };
loto p[1000000];
int v[101],u,S,n;
bool cmp(loto a,loto b)
{
    return a.sum<b.sum;
}
int cautbin(int sum)
{
    int i, pas=1<<19;
    for(i=0;pas!=0;pas>>=1)
        if(i+pas<u&&p[i+pas].sum+sum<=S)
            i+=pas;
    if(p[i].sum+sum==S)
        return i;
    else return -1;
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    int i,j,k,poz;
    scanf("%d%d",&n,&S);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);


    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++)
            {
                p[++u].sum=v[i]+v[j]+v[k];
                p[u].i=i;p[u].j=j;p[u].k=k;
            }
    sort(p+1,p+u+1,cmp);
    for(i=1;i<=u;i++)
    {
        poz=cautbin(p[i].sum);
        if(poz!=-1)
        {
            printf("%d %d %d %d %d %d",p[i].i,p[i].j,p[i].k,p[poz].i,p[poz].j,p[poz].k);
            return 0;
        }
    }
    printf("-1");
}