Cod sursa(job #166946)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 28 martie 2008 18:15:25
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
int a[101],n,s,nr=0,sum[1100000];
void scrie(int suma){
    int i,j,k;
    for (i=1;i<=n;i++)
     for (j=1;j<=n;j++)
      for (k=1;k<=n;k++)
       if (a[i]+a[j]+a[k]==suma)
        {printf("%d %d %d",a[i],a[j],a[k]);
         return;}
}
void qsort(int ls,int ld){
    int i=ls,j=ld,x=sum[(ls+ld)/2];
    do { while (sum[i]<x) i++;
         while (sum[j]>x) j--;
         if (i<=j) {int aux=sum[i];sum[i]=sum[j];sum[j]=aux;
                    i++;j--;}
       }
       while (i<=j);
    if (j>ls) qsort(ls,j);
    if (i<ld) qsort(i,ld);
}
int gasit(int ls,int ld,int x){
    int lo=ls,hi=ld,mij;
    while (lo<=hi) {mij=(lo+hi)/2;
                    if (sum[mij]==x) return mij;
                    if (sum[mij]<x) lo=mij+1;
                                else hi=mij-1;}
    if (lo>hi) return 0;
    }
int main(){
    int i,j,k;
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d %d",&n,&s);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    for (i=1;i<=n;i++)
     for (j=1;j<=n;j++)
      for (k=1;k<=n;k++)
       sum[++nr]=a[i]+a[j]+a[k];
    qsort(1,nr);
    for (i=1;i<=n;i++)
     for (j=1;j<=n;j++)
      for (k=1;k<=n;k++)
       if (gasit(1,nr,s-a[i]-a[j]-a[k])!=0)
        {printf("%d %d %d ",a[i],a[j],a[k]);
         scrie(s-a[i]-a[j]-a[k]);
         return 0;
        }
    printf("%d",-1);
    return 0;
}