Cod sursa(job #1369095)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 2 martie 2015 21:44:23
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#define nmax 105
#define hash 66013
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
int n,s,s1,a[nmax],m;
struct suma {int s;int i;int j;int k;};
suma v[nmax*nmax*nmax];
multiset <int> sol;

int cautbin(int x)
{
    int st,dr,mid;
    st=1;dr=m;
    while (st<=dr) {
        mid=(st+dr)>>1;
        if (x==v[mid].s)
            return mid;
        if (x>v[mid].s)
            st=mid+1;
        else
            dr=mid-1;
    }
    return -1;

}
bool compare(const suma &x, const suma &y)
{
    return x.s<y.s;
}
int main()
{
    int i,j,k,t;
    f>>n>>s;
    for (i=1;i<=n;i++)
        f>>a[i];
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            for (k=1;k<=n;k++) {
                    m++;
                    v[m].i=i;
                    v[m].j=j;
                    v[m].k=k;
                    v[m].s=a[i]+a[j]+a[k];
            }
    sort(v+1,v+m+1,compare);

    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            for (k=1;k<=n;k++) {
                    s1=s-a[i]-a[j]-a[k];
                    t=cautbin(s1);
                    if (t!=-1) {
                        sol.insert(a[i]);
                        sol.insert(a[j]);
                        sol.insert(a[k]);
                        sol.insert(v[t].i);
                        sol.insert(v[t].j);
                        sol.insert(v[t].k);
                        for (set <int> ::iterator it=sol.begin();it!=sol.end();it++)
                            g<<*it<<' ';
                        return 0;
                    }
            }

    g<<-1<<'\n';
    return 0;
}