Pagini recente » Cod sursa (job #2191182) | Cod sursa (job #3199686) | Cod sursa (job #1951038) | Cod sursa (job #2634680) | Cod sursa (job #2434042)
#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];
void addPartialSum(int *size, int sum, int firstNumber, int secondNumber, int thirdNumber)
{
(*size) ++;
set[(*size) - 1].sum = sum;
set[(*size) - 1].firstNumber = firstNumber;
set[(*size) - 1].secondNumber = secondNumber;
set[(*size) - 1].thirdNumber = thirdNumber;
}
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 = 0; j < N; j++)
for(int k = 0; k < N; k++)
{
int partial_sum = array[i] + array[j] + array[k];
if (partial_sum < S)
addPartialSum(&size, partial_sum, array[i], array[j], array[k]);
}
int answer[6], status = -1;
for (int i = 0; i < size; i++)
{
status = binarySearch(set, 0, size, 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;
qsort(answer, 6, sizeof(int), compare);
for(int j = 0; j < 6; j++)
{
if (j != 5)
fprintf(write, "%d ", answer[j]);
else
fprintf(write, "%d\n", answer[j]);
}
break;
}
}
if (status == -1)
fprintf(write, "-1\n");
fclose(read);
fclose(write);
return 0;
}