Cod sursa(job #458030)

Utilizator h_istvanHevele Istvan h_istvan Data 22 mai 2010 18:16:17
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#define FOR(i,a,b) for(i=a;i<=b;++i)
#define MAXN 101

using namespace std;

struct resz
{
       int val;
       int x,y,z;
}temp;

int n,i,j,k,s,x;
int v[MAXN];
vector<resz> a;

int cmp(resz a,resz b)
{
    return (a.val < b.val);
}

int keres(int x)
{
    if (x <= 0) return -1;
    
    int bal = 0,jobb = a.size()-1,kozep;
    while (bal < jobb)
    {
          kozep = (bal+jobb)/2;
          if (a[kozep].val < x) bal = kozep+1; else
          if (a[kozep].val > x) jobb = kozep-1; 
          else return kozep;
    }
    
    return -1;
}

int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    
    scanf("%d %d\n",&n,&s);
    FOR (i,1,n)
        scanf("%d\n",&v[i]);
        
    FOR (i,1,n)
        FOR (j,i,n)
            FOR (k,j,n)
            {
                temp.val = v[i]+v[j]+v[k];
                temp.x = i;
                temp.y = j;
                temp.z = k;
                a.push_back(temp);
            }
    
    sort(a.begin(),a.end(),cmp);
    
    FOR (i,1,n)
        FOR (j,i,n)
            FOR (k,j,n)
            {
                x = keres(s-(v[i]+v[j]+v[k]));
                if (x >= 0)
                {
                   printf("%d %d %d %d %d %d\n",v[i],v[j],v[k],v[a[x].x],v[a[x].y],v[a[x].z]);
                   return 0;
                }
            }
            
    printf("-1\n");
    
    
    return 0;
}