Cod sursa(job #1160248)

Utilizator MacWonkMihai Alexandru Cosmin MacWonk Data 30 martie 2014 13:26:13
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
long long n,i,j,t,ok,st,dr,m,S,k;
int a[105];
struct sume
{
    int i,j,t;
    long long s;
}v[300005];
int cmp(sume a, sume b)
{
    if(a.s>b.s) return 0;
    return 1;
}
int main()
{
    f>>n>>S;
    for(i=1;i<=n;++i) f>>a[i];
    for(i=1;i<=n;++i)
    {
        for(j=i;j<=n;++j)
        {
            for(t=j;t<=n;++t)
            {
               ++k;
               v[k].s=a[i]+a[j]+a[t];
               v[k].i=i;
               v[k].j=j;
               v[k].t=t;
            }
        }
    }
    sort(v+1,v+1+k,cmp);
    ok=0;
    for(i=1;i<=k&&ok==0;++i)
    {
        st=1; dr=k;
        while(st<=dr&&ok==0)
        {
            m=(dr+st)/2;
            if(v[m].s==S-v[i].s)
            {
                ok=1;
                g<<a[v[i].i]<<" "<<a[v[i].j]<<" "<<a[v[i].t]<<" "<<a[v[m].i]<<" "<<a[v[m].j]<<" "<<a[v[m].t]<<'\n';
            }
            else if(v[m].s>S-v[i].s) dr=m-1;
            else st=m+1;
        }
    }
    if(ok==0) g<<"-1"<<'\n';
    return 0;
}