Cod sursa(job #741862)

Utilizator CrescentselectJicol Crescent Crescentselect Data 27 aprilie 2012 11:28:33
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE * f=fopen("loto.in","r");
FILE * g= fopen("loto.out","w");

int n, suma,coef;
int *v,nr;
int *v_sume;

void sume()
{
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
        {
            for (k=j;k<=n;k++)
            {
                v_sume[++nr]=v[i]+v[j]+v[k];
            }
        }
    }
}
int cautbin(long long x)
{
    int i,pas=1<<17;
    for(i=0;pas!=0;pas>>=1)
    {
        if(i+pas<=nr && v_sume[i+pas]<=x)
        {
            i+=pas;
        }
    }
    if(v_sume[i] == x)
        return i;
    return -1;
}
void sol(long long x)
{
    int i,j,k,r;
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for (k=j;k<=n;k++)
            {
                r= cautbin(suma-(v[i]+v[j]+v[k]));
                if(r!=-1)
                {
                    fprintf(g,"%d %d %d ",v[i],v[j],v[k]);
                    return;
                }
            }
}
void afis1()
{
    int i,j,k,r;
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
        {
            for (k=j;k<=n;k++)
            {
                r= cautbin(suma-(v[i]+v[j]+v[k]));
                if(r!=-1)
                {
                    fprintf(g,"%d %d %d ",v[i],v[j],v[k]);
                    sol(suma-(v[i]+v[j]+v[k]));
                    return;
                }

            }
        }
    }
    fprintf(g,"-1");
}
int main()
{
    fscanf(f,"%d",&n);
    fscanf(f,"%d",&suma);
    v = new int (n+1);
    coef=n*n*n;
    v_sume= new int (coef);
    int i;
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d",&v[i]);
    }
    sume();
    sort(&v_sume[1],&v_sume[n+1]);
    afis1();

    fclose(f);
    fclose(g);
    return 0;
}