Cod sursa(job #1180551)

Utilizator heracleRadu Muntean heracle Data 30 aprilie 2014 18:59:20
Problema Loto Scor 100
Compilator cpp Status done
Runda lab10d30aprilie2014 Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;
FILE *fin=fopen("loto.in", "r");
ofstream fout("loto.out");

unsigned const maxb=8192;
char buf[maxb];
int ptr=maxb-1;

int getInt()
{
    int nr=0;
    while(buf[ptr]>'9' || buf[ptr]<'0')
    {
        if(++ptr>=maxb)
            fread(buf, maxb, 1, fin), ptr=0;
    }
    while(buf[ptr]<='9' && buf[ptr]>='0')
    {
        nr=nr*10+buf[ptr]-'0';
        if(++ptr>=maxb)
            fread(buf, maxb, 1, fin), ptr=0;
    }
    return nr;
}


int G[1000040], d;

int v[105];
int n, S, i, j, k, s;
inline void ack(int x)
{
    G[++d]=x;
}

bool cauta(int el)
{
    int st=1;
    int dr=d, mid;
    while(st<=dr)
    {
        mid=(st+dr)>>1;
        if(G[mid]==el)
        {
            return 1;
        }
        if(G[mid]>el)
            dr=mid-1;
        else
            st=mid+1;
    }
    return 0;
}

int main()
{

    n=getInt();
    S=getInt();

    for(i=1;i<=n;i++)
    {
        v[i]=getInt();
    }
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
        {
            for(k=j;k<=n;k++)
            {
                if(v[i]+v[j]+v[k]<=S)
                ack(v[i]+v[j]+v[k]);
            }
        }
    }

    sort(G+1, G+d+1);
    int x=-1;
    for(i=1;i<=d;i++)
    {
        if(cauta(S-G[i]))
        {
            x=G[i];
        }
    }
    if(x==-1)
        fout<<"-1";
    else{
            int h=1;
        for(i=1;i<=n && h;i++)
        {
            for(j=i;j<=n && h;j++)
            {
                for(k=j;k<=n && h;k++)
                {
                    if(v[i]+v[j]+v[k]==S-x)
                        {
                            fout<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
                            h=0;
                        }
                }
            }
        }
            h=1;
        for(i=1;i<=n && h;i++)
        {
            for(j=i;j<=n && h;j++)
            {
                for(k=j;k<=n && h;k++)
                {
                    if(v[i]+v[j]+v[k]==x)
                        {
                            fout<<v[i]<<" "<<v[j]<<" "<<v[k]<<"\n";
                            h=0;
                        }
                }
            }
        }

    }

}