Cod sursa(job #1510442)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 24 octombrie 2015 23:15:13
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

struct numere{
    int x,y,z,sum;
};

numere s[1000003];
ifstream in("loto.in");
ofstream out("loto.out");

bool functie(numere A, numere B)
{
    if(A.sum>B.sum)
        return 1;
    else return 0;
}

int n,suma;
int p = 0;
int a[103];
int v[8];

int main()
{
    in>>n>>suma;
    for (int i=1;i<=n;i++)
        in>>a[i];
    sort(a+1, a+n+1);
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++)
            for (int z=j;z<=n;z++){
                p++;
                s[p].x=a[i];
                s[p].y=a[j];
                s[p].z=a[z];
                s[p].sum=a[i]+a[j]+a[z];

            }
    sort (s+1,s+p+1,functie);
    int st,dr,s2,m,poz1,poz2;
    int ok = 0;
   for(int i=1; i<=p; i++)
    {
        st=1;
        dr=p;
        s2=suma-s[i].sum;
        poz1=i;

        while (st<=dr){
            m=(st+dr)/2;
            if(s[m].sum==s2)
            {
                poz2=m;
                ok=1;
                break;
            }
            if(s[m].sum>s2)
                dr=m-1;
            if(s[m].sum<s2)
                st=m+1;

        }
        if(ok==1)
            break;
    }
    if (ok==1){
        v[1]=s[poz1].x;
        v[2]=s[poz1].y;
        v[3]=s[poz1].z;
        v[4]=s[poz2].x;
        v[5]=s[poz2].y;
        v[6]=s[poz2].z;
        sort (v+1,v+7);
        for (int i=1;i<7;i++)
            out<<v[i]<<" ";
    }
    else
        out<<-1;
    return 0;
}