Cod sursa(job #1074620)

Utilizator teodor98Teodor Sz teodor98 Data 7 ianuarie 2014 19:44:43
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <algorithm>
#include <cstdlib>
using namespace std;
ifstream in("loto.in");
ofstream out("loto.out");
struct sume{
int suma;
int i;
int j;
int k;
};

int *v,s,n,nr;
sume *sum;
bool sort_sume(const sume  &a, const sume &b)
{
    return (a.suma < b.suma);
}
int cautbin(int s)
{
    int i=0, pas = 1 << 17;
    while(pas!=0)
    {

        if(i+pas <=nr && sum[i+pas].suma<=s)
        {
            i+=pas;
        }
        pas/=2;
    }
    return i;
}
int main()
{
    in >> n >> s;
    v = (int *) malloc(sizeof(int)*(n+1));
    sum = (sume *) malloc(sizeof(sume)*((n+1)*(n+1)*(n+1)));

    for(int i=1;i<=n;i++)
        in >> v[i];
    in.close();


    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            for(int k=j;k<=n;k++)
                    {
                        sum[++nr].suma = v[i]+v[j]+v[k];
                        sum[nr].i = v[i];
                        sum[nr].j = v[j];
                        sum[nr].k = v[k];
                    }
    sort(sum+1,sum+nr+1,sort_sume);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
            {
                int x = cautbin(s-v[i]-v[j]-v[k]);
                if(sum[x].suma == s-v[i]-v[j]-v[k])
                {
                    out << v[i] << " " << v[j] <<" " << v[k] << " " << sum[x].i << " " << sum[x].j << " "<< sum[x].k;
                    out.close();
                    return 0;
                }
            }

    out << -1<<"\n";
    //---------

    out.close();
    return 0;
}