Cod sursa(job #884005)

Utilizator PavelPavel Ana-Oriana Pavel Data 20 februarie 2013 16:39:10
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#include <algorithm>

using namespace std;
int v[103];
struct sume
{
    int x,y,z,s;
};
sume r[102];

bool cmp(sume a, sume b)
{
    if(a.s <= b.s)
        return true;
    return false;
}
int cautbin(int suma,int n)
{
    int i,pas=1<<20;
    for(i=0 ; pas != 0 ; pas/=2)
        if((i+pas) <= n && r[i+pas].s <= suma)
            i+=pas;
    return i;
}
int main()
{
    FILE *in = fopen("loto.in","r");
    FILE *out = fopen("loto.out","w");
    int n,sum,size=0,i,j,k,t;
    fscanf(in,"%d%d",&n,&sum);
    for(i=1 ; i<=n ; i++)
        fscanf(in,"%d",&v[i]);
    for(i=1 ; i<=n ; i++)
        for(j=i ; j<= n ; j++)
            for(k=j ; k<=n ; k++){
                size++;
                r[size].x=v[i];
                r[size].y=v[j];
                r[size].z=v[k];
                r[size].s=v[i]+v[j]+v[k];
            }
    sort(r + 1 , r + size + 1 , cmp);
    for(i=1 ; i <= size ; i++)
    {
        t=cautbin(sum-r[i].s,size);
        if(r[i].s+r[t].s == sum)
        {
            fprintf(out,"%d %d %d %d %d %d\n",r[i].x,r[i].y,r[i].z,r[t].x,r[t].y,r[t].z);
            return 0;
        }
    }
    fprintf(out,"-1\n");
    return 0;
}