Cod sursa(job #1468127)

Utilizator MrTudorTudor Savulescu MrTudor Data 5 august 2015 11:53:59
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("loto.in");
ofstream out("loto.out");
int N,S,i,j,z,a[101],v[1000012],ab,x;
int cautbin(int caut, int st,int dr)
{
    int mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]==caut) return mij;
        if(caut<v[mij]) dr=mij-1;
        else st=mij+1;
    }
    return -1;
}
int main()
{
    in>>N>>S;
    for(i=1; i<=N; ++i) in>>a[i];
    for(i=1; i<=N; ++i)
        for(j=1; j<=N; ++j)
            for(z=1; z<=N; ++z) v[++x]=a[i]+a[z]+a[j];
    sort(v+1,v+x+1);
    for(i=1; i<=N*N*N; ++i) if(cautbin(S-v[i],1,N*N*N)!=-1) ab=v[i],i=N*N*N+1;
    if(!ab) out<<-1;
    else
    {
        for(i=1; i<=N; ++i)
            for(j=1; j<=N; ++j)
                for(z=1; z<=N; ++z) if(ab==a[i]+a[z]+a[j])
                    {
                        out<<a[i]<<" "<<a[j]<<" "<<a[z]<<" ";
                        i=j=z=N+1;
                    }
        for(i=1; i<=N; ++i)
            for(j=1; j<=N; ++j)
                for(z=1; z<=N; ++z) if(S-ab==a[i]+a[z]+a[j])
                    {
                        out<<a[i]<<" "<<a[j]<<" "<<a[z]<<" ";
                        i=j=z=N+1;
                    }
    }
    out.close();
    return 0;
}