Cod sursa(job #1111355)

Utilizator DenisacheDenis Ehorovici Denisache Data 18 februarie 2014 20:16:04
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");

int N,S,v[110],nr;
struct point{int val,i,j,k;}w[1000099];

bool cmp(const point &A,const point &B)
{
    return A.val<B.val;
}

inline int CB(const int &X)
{
    int st=1,dr=nr;
    while(st<=dr)
    {
        int mij=(st+dr)>>1;
        if(w[mij].val==X)return mij;
        else if(w[mij].val>X)dr=mij-1;
            else st=mij+1;
    }
    return 0;
}
int main()
{
    f>>N>>S;
    for(int i=1;i<=N;++i)f>>v[i];
    sort(v+1,v+1+N);
    for(int i=1;i<=N;++i)
        for(int j=i;j<=N;++j)
            for(int k=j;k<=N;++k)
            {
                w[++nr].val=v[i]+v[j]+v[k];
                w[nr].i=i,w[nr].j=j,w[nr].k=k;
            }
    sort(w+1,w+1+nr,cmp);
    for(int i=1;i<=N;++i)
        for(int j=i;j<=N;++j)
            for(int k=j;k<=N;++k)
            {
                int aux=S-v[i]-v[j]-v[k];
                int poz=CB(aux);
                if(poz)
                {
                    g<<v[i]<<" "<<v[j]<<" "<<v[k]<<" "<<v[w[poz].i]<<" "<<v[w[poz].j]<<" "<<v[w[poz].k]<<'\n';
                    return 0;
                }
            }
    g<<-1<<'\n';
    return 0;
}