Cod sursa(job #64300)

Utilizator FlorianFlorian Marcu Florian Data 2 iunie 2007 15:20:06
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include<stdio.h>
long a[505],v[100001],n,s,p,b[100001],c[100001],d[100001];
FILE*f=fopen("loto.in","r");
FILE*g=fopen("loto.out","w");
void read()
        {
        long i,j,k;
        fscanf(f,"%ld %ld",&n,&s);
        for(i=1;i<=n;++i)
                {
                fscanf(f,"%ld",&a[i]);
                }
        for(i=1;i<=n;++i)
                for(j=i;j<=n;++j)
                        for(k=j;k<=n;++k)
                        {
                        v[++p]=a[i]+a[j]+a[k];
                        b[p]=i;
                        c[p]=j;
                        d[p]=k;
                        }
        }
void bubble()
        {
        long i,ok,aux;
        do
                {
                ok=1;
                for(i=1;i<p;++i)
                        {
                        if(v[i]>v[i+1])
                                {
                                aux=v[i]; v[i]=v[i+1]; v[i+1]=aux;
                                ok=0;
                                aux=c[i]; c[i]=c[i+1]; c[i+1]=aux;
                                aux=d[i]; d[i]=d[i+1]; d[i+1]=aux;
                                aux=b[i]; b[i]=b[i+1];b[i+1]=aux;
                                }
                         }
               }
        while(ok==0);
        }
long binary_search(long x)
        {
        long i,j,m;
        i=0; j=p;
        while(i<=j)
                {
               m=(i+j)/2;
                if(x+v[m]==s) return m;
                else if(x+v[m]<s) i=m+1;
                else j=m-1;
                }
        return 0;
        }
long calcul()
        {
        long i,j,poz;
        for(i=1;i<=p;++i)
                {
                poz=binary_search(v[i]);
                 if(poz!=0)
                        {
                        fprintf(g,"%ld %ld %ld %ld %ld %ld",a[b[i]],a[c[i]],a[d[i]],a[b[poz]],a[c[poz]],a[d[poz]]);
                        return 1;
                        }
                }
        return 0;
        }
int main()
        {
        read();
        bubble();
        if(!calcul()) fprintf(g,"-1");
        return 0;
        }