Cod sursa(job #136608)

Utilizator igorPirnau Igor igor Data 15 februarie 2008 18:20:35
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <stdio.h>   
#include <stdlib.h>   
  
int n,s,a[110],b[1001000],z;   
  
int cmp(const void *a, const void *b)   
{   
    return ( *(int*)a - *(int*)b );   
}   
  
void write(int x)   
{   
    int i,j,k;   
    for (i=1; i<=n; ++i)   
    {   
        for (j=i; j<=n; ++j)   
        {   
            for (k=j; k<=n; ++k)   
            {   
                if (a[i]+a[j]+a[k]==b[x])   
                {   
                    printf("%d %d %d",a[i],a[j],a[k]);   
                    return;   
                }   
            }   
        }   
    }   
}   
  
int main()   
{   
    freopen("loto.in","r",stdin);   
    freopen("loto.out","w",stdout);   
    scanf("%d%d",&n,&s);   
    int i,j,k;   
    for (i=1; i<=n; ++i) scanf("%d",&a[i]);   
    z=0;   
    for (i=1; i<=n; ++i)   
    {   
        for (j=i; j<=n; ++j)   
        {   
            for (k=j; k<=n; ++k)   
            {   
                ++z;   
                b[z]=a[i]+a[j]+a[k];   
            }   
        }   
    }   
    qsort(b+1,z, sizeof(int),cmp);   
    k=z;   
    for (i=1; i<=z && 0<k; ++i)   
    {   
        while(b[i]+b[k]>s && k>0)    
        {   
            k--;   
        }   
        if (k<=0) break;   
        if (b[i]+b[k]==s)    
        {      
            write(i);      
            printf(" ");      
            write(k);      
            printf("\n");      
            return 0;      
        }    
    }   
    printf("-1\n");   
    return 0;   
}