Pagini recente » Cod sursa (job #955266) | Cod sursa (job #2310492) | Cod sursa (job #2390407) | Cod sursa (job #333001) | Cod sursa (job #3310729)
/*
https://infoarena.ro/problema/loto
*/
#include <fstream>
using namespace std;
const int N = 100;
const int M = 666019;
const int NIL = -1;
struct nod
{
int info;
int urm;
};
int v[N];
nod v_nod[N*N*N];
int lst[M], n_v_nod;
void init_liste()
{
for (int i = 0; i < M; i++)
{
lst[i] = NIL;
}
}
bool exista(int val)
{
int c = val % M;
int p = lst[c];
while (p != NIL)
{
if (v_nod[p].info == val)
{
return true;
}
p = v_nod[p].urm;
}
return false;
}
void adauga(int val)
{
if (exista(val))
{
return;
}
v_nod[n_v_nod].info = val;
int c = val % M;
v_nod[n_v_nod].urm = lst[c];
lst[c] = n_v_nod++;
}
void sterge(int val)
{
if (!exista(val))
{
return;
}
int c = val % M;
int p = lst[c];
while (v_nod[p].info != val)
{
p = v_nod[p].urm;
}
v_nod[p].info = v_nod[lst[c]].info;
lst[c] = v_nod[lst[c]].urm;
}
void cauta(int s, int n, int &a, int &b, int &c)
{
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
for (int k = j; k < n; k++)
{
if (v[i] + v[j] + v[k] == s)
{
a = v[i];
b = v[j];
c = v[k];
return;
}
}
}
}
}
int main()
{
ifstream in("loto.in");
ofstream out("loto.out");
int n, s;
in >> n >> s;
for (int i = 0; i < n; i++)
{
in >> v[i];
}
init_liste();
///construim sumele de cate 3 elemente
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
for (int k = j; k < n; k++)
{
adauga(v[i] + v[j] + v[k]);
}
}
}
///cautam triplete cu suma dorita
bool ex = false;
for (int i = 0; i < n && !ex; i++)
{
for (int j = i; j < n && !ex; j++)
{
for (int k = j; k < n && !ex; k++)
{
if (exista(s - (v[i] + v[j] + v[k])))
{
ex = true;
out << v[i] << " " << v[j] << " " << v[k];
int a, b, c;
cauta(s - (v[i] + v[j] + v[k]), n, a, b, c);
out << " " << a << " " << b << " " << c << "\n";
}
}
}
}
if (!ex)
{
out << "-1\n";
}
in.close();
out.close();
return 0;
}