Cod sursa(job #1715486)

Utilizator denniscrevusDennis Curti denniscrevus Data 10 iunie 2016 20:43:08
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#include <algorithm>

using namespace std;

struct sume
    {
        int a;
        int b;
        int c;
        int suma;
    } sum[1000005],x,y;

bool comp(sume x, sume y)
    {
        return bool(x.suma<y.suma);
    }


int n,v[101],i,h,j,rez,rez1,rez2,rez3,s,k,dif,rez4,rez5,rez6,b;

int cautbin(int a)
        {
            int start=0,step=1;
            for(;step<=k;step<<=1);
            for(;step;step>>=1)
            {
                int index=start+step;
                if(index>k)
                    continue;
                if(sum[index].suma<=a)
                    start=index;
            }
        return start;
        }

int main()
{
    ifstream f("loto.in");
    ofstream g("loto.out");

    f>>n>>s;

    for(i=1;i<=n;i++)               //CITIRE
        f>>v[i];

    for(i=1;i<=n;i++)           //AUXILIAR
        for(j=i;j<=n;j++)
            for(h=j;h<=n;h++)
                {
                sum[++k].suma=v[i]+v[j]+v[h];
                sum[k].a=v[i];
                sum[k].b=v[j];
                sum[k].c=v[h];
                }
    sort(sum+1,sum+k+1,comp);

    for(i=1;i<=n;i++)
    {
        if(b==1)
            break;
        for(j=i;j<=n;j++)
        {
            if(b==1)
                break;
            for(h=j;h<=n;h++)
            {
                dif=s-v[i]-v[j]-v[h];
                rez=cautbin(dif);
                if(sum[rez].suma==dif)
                {
                    rez1=sum[rez].a;
                    rez2=sum[rez].b;
                    rez3=sum[rez].c;
                    rez4=v[i];
                    rez5=v[j];
                    rez6=v[h];
                    b=1;
                    break;
                }
            }
        }
    }



    if(b==1)
    g<<rez1<<" "<<rez2<<" "<<rez3<<" "<<rez4<<" "<<rez5<<" "<<rez6;
    else
        g<<"-1";
}