Cod sursa(job #1124101)

Utilizator Master011Dragos Martac Master011 Data 26 februarie 2014 11:19:56
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<cstdio>
#include<algorithm>
using namespace std;

const int Dmax = 1000000,MaxE = 100;
struct element{
    int sum,p1,p2,p3;
}v[Dmax + 1];
int a[MaxE+1];

bool cmp(element a, element b){
    return a.sum<b.sum;
}

int caut_bin (int x, int nr){
    int rez=0,pas=1<<30;
    while(pas){
        if(rez+pas<= nr && v[rez+pas].sum < x)
            rez+=pas;
        pas>>=1;
    }
    return rez;
}

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

    int n,nr=0,S;
    fscanf(in,"%d%d",&n,&S);
    for (int i = 1 ; i <= n ; ++i)  fscanf(in,"%d",&a[i]);

    for(int x = 1 ; x <= n ; ++x)
        for(int y = 1 ; y <= n ; ++y)
            for(int z = 1 ; z <= n ; ++z){
                v[++nr].sum=a[x]+a[y]+a[z];
                v[nr].p1=x;
                v[nr].p2=y;
                v[nr].p3=z;
            }
    sort(v+1,v+n+1,cmp);

    bool ok = true;
    int dr;
    for(int i = 1; i <= nr && ok ; ++i){
        dr=caut_bin(S-v[i].sum,nr);
        if(v[i].sum+v[dr+1].sum==S){
            ok=false;
            fprintf(out,"%d %d %d %d %d %d\n",v[i].p1,v[i].p2,v[i].p3,v[dr+1].p1,v[dr+1].p2,v[dr+1].p3);
        }
    }
    if(ok==true)
        fprintf(out,"-1\n");
    fclose(in);
    fclose(out);
    return 0;
}