Cod sursa(job #1470086)

Utilizator acomAndrei Comaneci acom Data 10 august 2015 13:06:47
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
#define NMAX 24577
ifstream fin("loto.in");
ofstream fout("loto.out");
vector <int> v[NMAX];
int n,s,a[105];
void adaugare(int nr)
{
    int i,num=nr%NMAX;
    for (i=0;i<v[num].size();++i)
        if (v[num][i]==nr)
            return ;
    v[num].push_back(nr);
}
bool cautare(int nr)
{
    int i,num=nr%NMAX;
    for (i=0;i<v[num].size();++i)
        if (v[num][i]==nr)
            return true;
    return false;
}
void gensol(int nr)
{
    int i,j,st,dr,mij,num;
    for (i=1;i<=n && a[i]<=nr;++i)
        for (j=i;j<=n && a[i]+a[j]<=nr;++j)
        {
            num=nr-a[i]-a[j];
            st=j, dr=n;
            while (st<=dr)
            {
                mij=(st+dr)>>1;
                if (a[mij]==num)
                {
                    fout<<a[i]<<" "<<a[j]<<" "<<a[mij]<<"\n";
                    return ;
                }
                if (a[mij]<num)
                    st=mij+1;
                else
                    dr=mij-1;
            }
        }
}
int main()
{
    int i,j,k;
    fin>>n>>s;
    for (i=1;i<=n;++i)
        fin>>a[i];
    sort(a+1,a+n+1);
    for (i=1;i<=n;++i)
        for (j=i;j<=n;++j)
            for (k=j;k<=n;++k)
                adaugare(a[i]+a[j]+a[k]);
    for (i=1;i<=n && a[i]<=s;++i)
        for (j=i;j<=n && a[i]+a[j]<=s;++j)
            for (k=j;k<=n && a[i]+a[j]+a[k]<=s;++k)
                if (cautare(s-(a[i]+a[j]+a[k])))
                {
                    fout<<a[i]<<" "<<a[j]<<" "<<a[k]<<" ";
                    gensol(s-(a[i]+a[j]+a[k]));
                    return 0;
                }
    fout<<"-1\n";
    return 0;
}