Pagini recente » Cod sursa (job #1768241) | Cod sursa (job #346959) | Cod sursa (job #1079518) | Cod sursa (job #1907881) | Cod sursa (job #2434110)
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define null NULL
#define in "loto.in"
#define out "loto.out"
typedef struct partial
{
int sum;
int firstNumber;
int secondNumber;
int thirdNumber;
}Sums;
int array[1000000];
Sums set[10000000];
int compare(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}
int binarySearch(Sums *set, int left, int right, int to_be_found)
{
if (left <= right)
{
int middle = left + (right - left) / 2;
if (set[middle].sum == to_be_found)
return middle;
if (set[middle].sum > to_be_found)
return binarySearch(set, left, middle, to_be_found);
else
return binarySearch(set, middle + 1, right, to_be_found);
}
return -1;
}
int main(int argc, char const *argv[])
{
FILE *read = (FILE *) fopen(in, "r");
FILE *write = (FILE *) fopen(out, "w");
int size = 0;
int N, S;
fscanf(read, "%d%d", &N, &S);
for (int i = 0; i < N; i++)
fscanf(read, "%d", &array[i]);
qsort(array, N, sizeof(int), compare);
for (int i = 0; i < N; i++)
for(int j = i; j < N; j++)
for(int k = j; k < N; k++)
{
int partial_sum = array[i] + array[j] + array[k];
if (partial_sum < S)
{
size++;
set[size - 1].sum = partial_sum;
set[size - 1].firstNumber = array[i];
set[size - 1].secondNumber = array[j];
set[size - 1].thirdNumber = array[k];
}
}
int answer[6], status = -1;
for (int i = 0; i < size; i++)
{
status = binarySearch(set, 0, size - 1, S - set[i].sum);
if (status != -1)
{
answer[0] = set[i].firstNumber;
answer[1] = set[status].firstNumber;
answer[2] = set[i].secondNumber;
answer[3] = set[status].secondNumber;
answer[4] = set[i].thirdNumber;
answer[5] = set[status].firstNumber;
fprintf(write, "%d %d %d %d %d %d\n", answer[0], answer[1], answer[2], answer[3], answer[4], answer[5]);
return 0;
}
}
if (status == -1)
fprintf(write, "-1\n");
return 0;
}