Cod sursa(job #1037880)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 20 noiembrie 2013 20:26:42
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>

using namespace std;

int N,S,v[105],lens;

struct Nr
{
    int i,j,k,suma;
};
Nr s[1000005];

inline void Read()
{
    int i,j,k;
    ifstream fin("loto.in");
    fin>>N>>S;
    for(i=1;i<=N;i++)
        fin>>v[i];
    fin.close();
    for(i=1;i<=N;i++)
        for(j=i;j<=N;j++)
            for(k=j;k<=N;k++)
            {
                lens++;
                s[lens].suma=v[i]+v[j]+v[k];
                s[lens].i=i; s[lens].j=j; s[lens].k=k;
            }
}

inline int BSearch(int x)
{
    int st,dr,mij;
    st=1;dr=lens;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(x==s[mij].suma)
            return mij;
        if(x<s[mij].suma)
            dr=mij-1;
        else
            st=mij+1;
    }
    return -1;
}

inline void Solve()
{
    int i,j,k,ok=0,poz;
    ofstream fout("loto.out");
    for(i=1;i<=N;i++)
        for(j=i;j<=N;j++)
            for(k=j;k<=N;k++)
            {
                poz=BSearch(S-v[i]-v[j]-v[k]);
                if(poz>0)
                {
                    fout<<v[i]<<" "<<v[j]<<" "<<v[k]<<" "<<v[s[poz].i]<<" "<<v[s[poz].j]<<" "<<v[s[poz].k]<<"\n";
                    ok=1; return ;
                }
            }
    if(!ok)
        fout<<"-1\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}