Cod sursa(job #365216)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 18 noiembrie 2009 09:44:09
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct numere
{
    int a,b,c;
};
int i,u,v[105],s1,sum,s[1000005],s2,aux,n,j,t,st,dr,ok,m,maxi;
numere nume[105];
int main ()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&n,&sum);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        if(v[i]>maxi)
            maxi=v[i];
    }
    if(maxi*6<sum)
    {
        printf("-1");
        return 0;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(t=1;t<=n;t++)
            {
                s[++u]=v[i]+v[j]+v[t];
                nume[u].a=i;nume[u].b=j;
                nume[u].c=t;
            }
    sort(s+1,s+u+1);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(t=1;t<=n;t++)
            {
                s2=v[i]+v[j]+v[t];s1=sum-s2;
                st=1;
                dr=u;ok=0;
                while(st<=dr)
                {
                    m=(st+dr)/2;
                    if(s1<s[m])
                        dr=m-1;
                    else
                        if(s1>s[m])
                            st=m+1;
                    else
                    {
                        ok=1;
                        break;
                    }
               }
               if(ok)
               {
                    printf("%d %d %d %d %d %d",i,j,t,nume[m].a,nume[m].b,nume[m].c);
                    return 0;
               }
           } //for
    printf("-1");
    return 0;
}