Cod sursa(job #2276344)

Utilizator alexradu04Radu Alexandru alexradu04 Data 4 noiembrie 2018 16:56:54
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>	
const int MAXN = 100 + 5,MAX_SUM = 6e8 + 5;
using namespace std;
ifstream fin("loto.in"); ofstream fout("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 || !suma_cautata)
        return -1;
    else
        return ans;
}
 
bool cmp(info a,info b)
{	
    return a.suma < b.suma;	
}
	
int main()	
{
    fin>>n>>sum_maxima;	
    for(int i = 1; i <= n; i++)
         fin>>v[i];
    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]);
    sort(sume + 1,sume + cate_sume,cmp);
    for(int i = 1; i <= cate_sume; i++){
        int ans = cautare_binara(sum_maxima - sume[i].suma);
        if(ans != -1)
        {
            fout << sume[i].a<<" "<<sume[i].b<<" "<<sume[i].c
            <<" "<<sume[ans].a<<" "<<sume[ans].b<<" "<<sume[ans].c;
            return 0;
        }
    }
	fout << -1;
    return 0;
}