Cod sursa(job #1311041)
Utilizator | 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;
}