Cod sursa(job #69053)

Utilizator infogodinfo god infogod Data 30 iunie 2007 21:28:19
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
//100 de puncte
#include<stdlib.h>
#include<stdio.h>
FILE*f=fopen("loto.in","r");
FILE*g=fopen("loto.out","w");
typedef struct
        {
        int b,i,j,k;
        }element;
element v[500002];
long n,p=0;
long s;
int c[1002];
void read()
        {
        long i;
        fscanf(f,"%ld %ld",&n,&s);
        for(i=0;i<n;++i) fscanf(f,"%d",&c[i]);
        long j,k;
        for(i=0;i<n;++i)
               for(j=i;j<n;++j)
                        for(k=j;k<n;++k)
                         {
                         v[p].b=c[i]+c[j]+c[k];
                         v[p].i=i; v[p].j=j; v[p].k=k;
                         p++;
                         }
        p--;
        }
int intcmp(const void *a, const void *b)
        {
        return *(int*)a-*(int*)b;
        }
long binary_search(long x, long k)
        {
        long j,i,m;
        i=k; j=p;
        while(i<=j)
                {
                m=(i+j)/2;
                if(v[m].b+x==s) return m;
                else if (v[m].b+x<s) i=m+1;
                else j=m-1;
                }
        return -2;
        }
void bug()
        {
        int i;
        fprintf(g,"\n");
        fprintf(g,"\n");
        for(i=0;i<=p;++i) fprintf(g,"%d ",v[i].b);
         }
int calcul()
        {
        long i,ok=0,x;
        qsort(v,p,sizeof(v[0]),intcmp);
        for(i=0;i<=p;++i)
                {
        x=binary_search(v[i].b,i);
                if(x!=-2)
                        {
                        ok=1;
                         fprintf(g,"%d %d %d %d %d %d",c[v[i].i],c[v[i].j],c[v[i].k],c[v[x].i],c[v[x].j],c[v[x].k]);
                        return 0;
                        }
                 }
        fprintf(g,"-1");
        return 0;
        }
int main()
        {
        read();
        calcul();
        return 0;
        }