Cod sursa(job #1121779)

Utilizator alexpascadiAlexandru Pascadi alexpascadi Data 25 februarie 2014 14:01:16
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

struct suma
{
    int val;
    int a,b,c;
};

const int N=101;
int v[N],poz[N*N*N],nr;
suma sume[N*N*N];


int cauta(int s)
{
    int sol=0,pas=1<<20;
    while(pas>0)
    {
        if(sol+pas<=nr && sume[poz[sol+pas]].val<=s)
            sol+=pas;
        pas>>=1;
    }
    return sol;
}


bool cmp(int x, int y)
{
    if(sume[poz[x]].val<sume[poz[y]].val) return 1;
    return 0;
}

int main()
{
    FILE *in=fopen("loto.in","r");
    FILE *out=fopen("loto.out","w");

    int n,s,nsume,i,j,k;
    nr=0;
    bool gasit=0;
    fscanf(in,"%d%d",&n,&s);

    for(i=1;i<=n;i++)
    {
        fscanf(in,"%d",&v[i]);
    }

    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++)
            {
                nr++;
                sume[nr].val=v[i]+v[j]+v[k];
                sume[nr].a=i;
                sume[nr].b=j;
                sume[nr].c=k;
            }

    for(i=1;i<=nr;i++) poz[i]=i;
    sort(poz+1,poz+nr+1,cmp);

    //printf("nr=%d\n",nr);

    for(i=1;i<=(nr>>1) && gasit==0;i++)
    {
        j=cauta(s-sume[poz[i]].val);
        if(sume[poz[i]].val + sume[poz[j]].val == s) gasit=1;
        //printf("gasit=%d, i=%d, j=%d\n",gasit,i,j);
    }
    i--;

    if(gasit)
    {
        fprintf(out,"%d %d %d ",v[sume[poz[i]].a],v[sume[poz[i]].b],v[sume[poz[i]].c]);
        fprintf(out,"%d %d %d",v[sume[poz[j]].a],v[sume[poz[j]].b],v[sume[poz[j]].c]);
    }
    else
        fprintf(out,"-1");

    return 0;
}