Cod sursa(job #2260911)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 15 octombrie 2018 19:04:49
Problema Loto Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <algorithm>

const int MAXN = 100 + 5,MAX_SUM = 6e8 + 5;

using namespace std;

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

int n,v[MAXN],sum_maxima,cate_sume;

struct info{
    int suma,a,b,c;
}sume[MAXN*MAXN*MAXN];

void add_suma(int a,int b,int c){
    sume[++cate_sume] = {
        a + b + c, a, b, c,
    };
}
int cautare_binara(int suma_cautata){
    int pas = 1<<20,ans = 0;

    while(pas){
        if(ans + pas <= cate_sume && sume[ans + pas].suma <= suma_cautata)
            ans += pas;
        pas /= 2;
    }
    if(sume[ans].suma != suma_cautata)
        return -1;
    else
        return ans;
}

int main()
{
    in>>n>>sum_maxima;
    for(int i = 1; i <= n; i++)
        in>>v[i];

    int s;
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            for(int k = j; k <= n; k++)
                add_suma(v[i],v[j],v[k]);
    for(int i = 1; i <= cate_sume; i++){
        int ans = cautare_binara(sum_maxima - sume[i].suma);
        if(ans != -1){
            out<<sume[i].a<<" "<<sume[i].b<<" "<<sume[i].c<<" "<<sume[ans].a<<" "<<sume[ans].b<<" "<<sume[ans].c;
            return 0;
        }
    }
    out<<-1;
    return 0;
}