Cod sursa(job #1689416)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 14 aprilie 2016 11:04:31
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <algorithm>
#define SUM first.first
#define NR1 first.second
#define NR2 second.first
#define NR3 second.second

using namespace std;
pair <pair <int,int>,pair <int,int> > v[1000001];
int w[101];
int main()
{
    FILE *fin=fopen ("loto.in","r");
    FILE *fout=fopen ("loto.out","w");
    int n,s,i,h,j,k,st,dr,mid,suma;
    fscanf (fin,"%d %d",&n,&s);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d",&w[i]);
    h=1;
    for (i=1;i<=n;i++)
        for (j=i;j<=n;j++)
            for (k=j;k<=n;k++){
                v[h].SUM=w[i]+w[j]+w[k];
                v[h].NR1=w[i];
                v[h].NR2=w[j];
                v[h].NR3=w[k];
                h++;
            }
    sort (v+1,v+h+1);
    for (i=1;i<=n;i++)
        for (j=i;j<=n;j++)
            for (k=j;k<=n;k++){
                suma=s-w[i]-w[j]-w[k];
                // cautam binar suma sum in vectorul nostru
                st=1;
                dr=n;
                while (st<=dr){
                    mid=(st+dr)/2;
                    if (v[mid].SUM<suma)
                        st=mid+1;
                    else if (v[mid].SUM==suma)
                        break;
                    else dr=mid-1;
                }
                if (st<=dr){
                    fprintf (fout,"%d %d %d %d %d %d",w[i],w[j],w[k],v[mid].NR1,v[mid].NR2,v[mid].NR3);
                    return 0;
                }
            }
    fprintf (fout,"-1");
    return 0;
}