Cod sursa(job #1035113)

Utilizator tavi.belu1994FMI Belu Andrei Octavian tavi.belu1994 Data 18 noiembrie 2013 12:22:22
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX 1000001
FILE *f,*g;
using namespace std;

struct suma
{
    int s, i, j, l;
}x[MAX];

void qsort(suma v[], int st, int dr)
{
      int i=st, j=dr;
      int piv = v[(st+dr)/2].s;
      while (i <= j)
      {
            while(v[i].s < piv)
                i++;
            while(v[j].s > piv)
                j--;
            if(i<=j)
            {
                  swap(v[i],v[j]);
                  i++;
                  j--;
            }
      }
      if (st < j) qsort(v, st, j);
      if (i < dr) qsort(v, i, dr);
}

int cautbin(suma v[], int n, int x)
{
    int st=1, dr=n, m;
    while(st<=dr)
    {   m=st+(dr-st)/2;
        if(v[m].s==x) return m;
        if(v[m].s>x) dr=m-1;
        else st=m+1;
    }
    return -1;
}

int main()
{
    f=fopen("loto.in","r");
    g=fopen("loto.out","w");
    int s,n,v[101],i,j,l,k;
    fscanf(f,"%d%d",&n,&s);
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d",&v[i]);
    }
    fclose(f);
    k=0;
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
        {
            for(l=j;l<=n;l++)
            {
                x[++k].s=v[i]+v[j]+v[l];
                if(x[k].s<s)
                {
                    x[k].i=v[i];
                    x[k].j=v[j];
                    x[k].l=v[l];
                }
            }
        }
    }

    qsort(x,1,k);

    for(i=1; i<=k; i++)
    {
        j=cautbin(x,k,s-x[i].s);
        if(j>0)
        {
            fprintf(g,"%d %d %d %d %d %d",x[i].i,x[i].j,x[i].l,x[j].i,x[j].j,x[j].l);
            fclose(g);
            return 0;
        }
    }

    fprintf(g,"-1");
    fclose(g);
    return 0;
}