Cod sursa(job #2405418)

Utilizator MariusblockMoga Marius-Ioan Mariusblock Data 14 aprilie 2019 14:43:36
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

struct ob{
    int x,y,z;
    int sum;
};

int n,m;
int v[102];
ob sums[1000005];

bool comp(ob a,ob b){
    if(a.sum < b.sum){
        return 1;
    }
    return 0;
}

int binarys(int st,int dr,int val){
    int m = st + (dr-st)/2;
    if(dr >= st){
        if(sums[m].sum == val){
            return m;
        }
        if(sums[m].sum < val){
            return binarys(m+1,dr,val);
        }
        if(sums[m].sum > val){
            return binarys(st,m-1,val);
        }
    }
    return -1;
}

int main()
{
    int i,j,k,d = 1;
    fin>>n>>m;
    for(i = 1; i <= n; i++){
        fin>>v[i];
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= i; j++){
            for(k = 1; k <= j; k++){
                sums[d].x = v[i];
                sums[d].y = v[j];
                sums[d].z = v[k];
                sums[d].sum = v[i] + v[j] + v[k];
                d++;
            }
        }
    }
    d--;
    int p;
    sort(sums + 1, sums + d+1,comp);
    for(i = 1; i <= d; i++){
        if(m - sums[i].sum < 0){
            break;
        }
        p = binarys(1,d+1,m - sums[i].sum);
        if(p != -1){
            fout<<sums[i].x<<" "<<sums[i].y<<" "<<sums[i].z<<" "<<sums[p].x<<" "<<sums[p].y<<" "<<sums[p].z<<" "<<endl;
            return 0;
        }
    }
    fout<<"-1"<<endl;
    return 0;
}