Cod sursa(job #597317)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 21 iunie 2011 19:49:55
Problema Loto Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <algorithm>
#include <cstdlib>


using namespace std;

int n,a[100],s,x;
ifstream f("loto.in");
ofstream g("loto.out");

typedef struct
{
    int val,a,b,c;
} comb;

comb b[1000000];
int poz=-1;;

bool ok(comb a, comb b)
{
    return a.val<b.val;
}

int caut_bin(int left, int right, int sum)
{
    int i=left, j=right, r;
    while (i<j)
    {
        r=(i+j)/2;
        if (b[r].val>=s-sum) j=r;
        else i=r+1;
    }
    x=i;
    return b[x].val;
}

int main()
{
    f >> n >> s;
    int i,j,k;
    for (i=0; i<n; i++)
        f >> a[i];
    for (i=0; i<n; i++)
    for (j=i; j<n; j++)
    for (k=j; k<n; k++)
    {
        b[++poz].val=a[i]+a[j]+a[k];
        b[poz].a=a[i];
        b[poz].b=a[j];
        b[poz].c=a[k];
    }
    sort(b,b+poz+1,ok);
    //for (i=0; i<=poz; i++)
      //  g << b[i].val << ' ' << b[i].a << ' ' << b[i].b << ' ' << b[i].c << endl;
    for (i=0; i<=poz; i++)
    {
        if (b[i].val+caut_bin(0,poz,b[i].val)==s) break;
    }
    g << ' ' << b[i].a << ' ' << b[i].b << ' ' << b[i].c << ' ' << b[x].a << ' ' << b[x].b << ' ' << b[x].c;
    return 0;
}