Cod sursa(job #1467426)

Utilizator vladttturcuman vlad vladtt Data 3 august 2015 13:30:22
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <algorithm>
#include <cstdlib>

using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

int i,j,k,n,m,s;

int a[200],sum[1000010],b[10];

struct pampam{

int t1,t2,t3;

}f[1000010];

bool comp(pampam a,pampam b)
{
    return a.t1+a.t2+a.t3<=b.t1+b.t2+b.t3;
}

void _write(int poz,int poz1)
{

    b[1]=f[poz].t1;
    b[2]=f[poz].t2;
    b[3]=f[poz].t3;
    b[4]=f[poz1].t1;
    b[5]=f[poz1].t2;
    b[6]=f[poz1].t3;

    sort(b+1,b+1+6);
    for(i=1;i<=6;i++)
        fout<<b[i]<<' ';

}


void caut_bin(int s,int poz1)
{

    int inc=1,mij,sf=m,p=0;
    while(inc<=sf)
    {

        mij=(inc+sf)/2;
        if(sum[mij]==s) {p=mij; break;}
        if(sum[mij]<s)
            inc=mij+1;
        else
            sf=mij-1;
    }

    if(p<=m && sum[p]==s)
    {
        _write(p,poz1);
        exit(0);
    }

}

int main()
{
    fin>>n>>s;

    for(i=1;i<=n;i++)
        fin>>a[i];

    sort(a+1,a+1+n);

    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++)
            {
                f[++m].t1=a[i];
                f[m].t2=a[j];
                f[m].t3=a[k];
                sum[m]=a[i]+a[j]+a[k];
            }

    sort(f+1,f+1+m,comp);

    sort(sum+1,sum+m+1);

    for(i=1;i<=m;i++)
        caut_bin(s-sum[i],i);

    fout<<-1;

    return 0;
}