Cod sursa(job #392796)

Utilizator KrillKnossisKuchiki Byakuya KrillKnossis Data 8 februarie 2010 12:28:28
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
 
const char in[]="loto.in";
const char out[]="loto.out";
const int N=105;
int s[3000000], v[N], S, n;
struct cmp{
    bool operator()(const int &a, const int &b)
    {
        return a<b;
    }
    };
 
 
 
void nr(int numar)
{
    int i, j, k;
   for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            for(k=1;k<=n;++k)
                if(v[i]+v[j]+v[k]==numar){
                    printf("%d %d %d ", v[i], v[j], v[k]);
                return;
                }
}
 
int main()
    {
        freopen(in,"r",stdin);
        freopen(out,"w",stdout);
        scanf("%d %d", &n, &S);
        int i, j, k;
        for(i=1;i<=n;++i)
            scanf("%d", &v[i]);
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
                for(k=1;k<=n;++k)
                    s[++v[0]]=v[i]+v[j]+v[k];
        sort(s+1, s+v[0]+1, cmp());
        int hi, lo, mid;
            for(i=1;i<=v[0];++i)
            {
               for(hi=v[0], lo=1; lo<=hi;)
                {
                    mid=lo+(hi-lo)/2;
                    if(s[mid] == S-s[i]){
                        nr(s[mid]), nr(s[i]);return 0;}
                    else {
                        if(s[mid]<S-s[i])lo=mid+1;
                        else hi=mid-1;
                    }
                }
            }
        printf("-1\n");
    return 0;
}