Cod sursa(job #882315)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 19 februarie 2013 00:10:48
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *f=fopen("loto.in","r"), *g=fopen("loto.out","w");

struct numere{
    long int val, unu, doi, trei;
}sume[1000005];

long int n, s, v[105], ind=0;

void citire(){
long int i;
    fscanf(f,"%ld %ld",&n,&s);
    for(i=1;i<=n;i++){
        fscanf(f,"%ld",&v[i]);
    }
}

void comb(){
long int i, j, k;

    for(i=1;i<=n;i++){
        for(j=i;j<=n;j++){
            for(k=j;k<=n;k++){
                ind++; sume[ind].unu=i; sume[ind].doi=j; sume[ind].trei=k; sume[ind].val=i+j+k;
            }
        }
    }

}

bool cmp(numere a, numere b){
    if(a.val<b.val){return 1;}
    return 0;
}

long int cb(long int w){
long int k1, k2, mij;

    k1=1; k2=ind;

    while(k1<k2){
        //printf("%ld %ld\n",k1,k2);
        mij= (k1+k2)/2;
        if(w==sume[mij].val){return mij;}
        else{
            if(w<sume[mij].val){k2=mij;}
            else{k1=mij;}
        }
        if(k1+1==k2 && w!=sume[k1].val && w!=sume[k2].val){return -1;}

    }
    return -1;
}

void rez(){
long int i, ok, afis=0;

    for(i=1;i<=ind;i++){ //printf("%ld\n",i);
        ok=cb(s-sume[ind].val);
        if(ok!=-1){afis=1;fprintf(g,"%ld %ld %ld %ld %ld %ld\n",sume[ind].unu,sume[ind].doi,sume[ind].trei,sume[ok].unu,sume[ok].doi,sume[ok].trei);break;}
    }
    if(afis==0){fprintf(g,"-1");}

}

int main(){

    citire();
    comb();
    sort(sume+1,sume+ind+1,cmp);
    rez();

return 0;
}