Pagini recente » Cod sursa (job #469309) | Cod sursa (job #2252096) | Cod sursa (job #183523) | Cod sursa (job #2502923) | Cod sursa (job #2623790)
// Infoarena - Loto
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
const int MAX_N = 1e2;
int arr[MAX_N];
struct sum_of_three{
int a, b, c;
int sum;
};
// sum_of_three sums[MAX_N * MAX_N * MAX_N];
std::vector <sum_of_three> sums;
int binarySearch(int sum)
{
if (sum < 0) {
return -1;
}
int left = 0;
int right = sums.size() - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (sums[mid].sum == sum) {
return mid;
}
if (sums[mid].sum < sum) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
int main()
{
std::ifstream fin("loto.in");
std::ofstream fout("loto.out");
int n, total_sum;
fin >> n >> total_sum;
for (int i = 0; i < n; ++i) {
fin >> arr[i];
}
// int sums_size = 0;
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
for (int k = j; k < n; ++k) {
// sums[++sums_size] = {arr[i], arr[j], arr[k], arr[i] + arr[j] + arr[k]};
sum_of_three current;
current.a = arr[i];
current.b = arr[j];
current.c = arr[k];
current.sum = arr[i] + arr[j] + arr[k];
sums.emplace_back(current);
}
}
}
// Sortez sumele pentru a putea cauta binar dupa
std::sort(sums.begin(), sums.end(),
[](const sum_of_three& A, const sum_of_three& B) -> bool {
return A.sum < B.sum;
});
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
for (int k = j; k < n; ++k) {
int position = binarySearch(total_sum - (arr[i] + arr[j] + arr[k]));
if (position != -1) {
fout << arr[i] << ' ' << arr[j] << ' ' << arr[k] << ' ' <<
sums[position].a << ' ' << sums[position].b << ' ' << sums[position].c << '\n';
return 0;
}
}
}
}
fout << "-1\n";
return 0;
}