Cod sursa(job #1311041)

Utilizator fulgerulnegruFMI Ekart Dragos-Ioan fulgerulnegru Data 7 ianuarie 2015 17:27:31
Problema Loto Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 5.82 kb
#include <algorithm>
#include <fstream>
 
using namespace std;
 
ifstream in("loto.in");
ofstream out("loto.out");
 
int v[101] , sume[1000001] , n;
 
void rest3(int scurent)
{
        int i , j , k;
         
            for(i = 1 ; i <= n ; i++)
                        for(j = i ; j <= n ; j++)
                                        for(k = j ; k <= n ; k++)
                                                        {
                                                                            if(v[i] + v[j] + v[k] == scurent)
                                                                                                {
                                                                                                                        out<<v[i]<<' '<<v[j]<<' '<<v[k]<<'\n';
                                                                                                                                            return;
                                                                                                                                                            }
                                                                                        }
}
 
int main()
{
        int s , i , j , k , l , pas , curent , scurent;
         
            in>>n>>s;
             
                for(i = 1 ; i <= n ; i++)
                            in>>v[i];
                 
                    sort(v + 1 , v + n + 1);
                     
                        curent = 1;
                            for(i = 1 ; i <= n ; i++)
                                        for(j = i ; j <= n ; j++)
                                                        for(k = j ; k <= n ; k++)
                                                                        {
                                                                                            sume[curent] = v[i] + v[j] + v[k];
                                                                                                            curent++;
                                                                                                                        }
                             
                                sort(sume + 1 , sume + curent);
                                 
                                    for(i = 1 ; i <= n ; i++)
                                                for(j = i ; j <= n ; j++)
                                                                for(k = j ; k <= n ; k++)
                                                                                {
                                                                                                    scurent = s - v[i] - v[j] - v[k];
                                                                                                                    l = 0;
                                                                                                                                    pas = 1 << 19;
                                                                                                                                                    while(pas)
                                                                                                                                                                        {
                                                                                                                                                                                                if(l + pas < curent && sume[l + pas] < scurent)
                                                                                                                                                                                                                            l += pas;
                                                                                                                                                                                                                    pas /= 2;
                                                                                                                                                                                                                                    }
                                                                                                                                                                    if(sume[l + 1] == scurent)
                                                                                                                                                                                        {
                                                                                                                                                                                                                out<<v[i]<<' '<<v[j]<<' '<<v[k]<<' ';
                                                                                                                                                                                                                                    rest3(scurent);
                                                                                                                                                                                                                                                        return 0;
                                                                                                                                                                                                                                                                        }
                                                                                                                                                                                }
                                     
                                        out<<-1<<'\n';
                                            return 0;
}