Cod sursa(job #504732)

Utilizator CS-meStanca Marian Ciprian CS-me Data 28 noiembrie 2010 15:48:30
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *fin, *fout;
int n,i,j,val[101],p,sum,k;
struct suma{
    int x;
    int y;
    int z;
    int s;
} s[1000000];

int cmp(suma a, suma b){
    if(a.s<b.s){
        return 1;
    }
    return 0;

}

int cautare_binara(int val){
int i,j,m;

    i=1;
    j=p;

    while(i<=j){
        m=(i+j)/2;
        if(val==s[m].s){
            return m;
        }
        else
        if(val<s[m].s){
            j=m-1;
        }
        else{
            i=m+1;
        }
    }

    return -1;
}

int main(){

    fin=fopen("loto.in","r");
    fout=fopen("loto.out","w");
    fscanf(fin,"%d %d",&n,&sum);
    for(i=1;i<=n;i++)
        fscanf(fin,"%d",&val[i]);
    p=0;
    for(i=1;i<=n;i++){
        for(j=i;j<=n;j++){
            for(k=j;k<=n;k++){
                p++;
                s[p].x=val[i];
                s[p].y=val[j];
                s[p].z=val[k];
                s[p].s=val[i]+val[j]+val[k];
            }
        }
    }

    sort(s+1,s+p+1,cmp);

    for(i=1;i<=p;i++){
        k=cautare_binara(sum-s[i].s);
        if(k!=-1){
            fprintf(fout,"%d %d %d %d %d %d", s[i].x, s[i].y, s[i].z, s[k].x, s[k].y, s[k].z);
            return 0;
        }
    }
    fprintf(fout,"-1");
    fclose(fout);
    fclose(fin);

return 0;
}