Pagini recente » Cod sursa (job #1061962) | Cod sursa (job #3121582) | Cod sursa (job #2741961) | Cod sursa (job #2792635) | Cod sursa (job #1266663)
#include "stdio.h"
#include "stdlib.h"
#define MAX 100000001
FILE *f, *g;
int nr[101];
int S;
int N;
typedef struct number {
int i;
int j;
int k;
int sum;
};
number n[1000001];
int index, size;
int ok;
/*
The function is used to merge two arrays:
arr[left..middle];
arr[middle+1..right];
of the array arr
*/
void merge(number* arr, int left, int middle, int right)
{
int i, j, k;
int n1 = middle - left + 1;
int n2 = right - middle;
/* create temporary arrays */
number *L, *R;
L = (number*)(malloc(n1 * sizeof(number)));
R = (number*)(malloc(n2 * sizeof(number)));
/* populate the two arrays L[] and R[] */
for(i = 0; i < n1; i++)
L[i] = arr[i+left];
for(j = 0; j < n2; j++)
R[j] = arr[j+1+middle];
/* merge the temporary arrays back into arr[left..right] */
i = 0;
j = 0;
k = left;
while(i < n1 && j < n2)
{
if(L[i].sum < R[j].sum)
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[] */
while(i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[] */
while(j < n2)
{
arr[k] = R[j];
j++;
k++;
}
free(L);
free(R);
}
void mergeSort(number* arr, int left, int right)
{
if(left < right)
{
int middle = left + (right - left) / 2;
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
merge(arr, left, middle, right);
}
}
int main()
{
f = fopen("loto.in", "r");
g = fopen("loto.out", "w");
fscanf(f, "%d", &N);
fscanf(f, "%d", &S);
for(int i = 1; i <= N; i++)
fscanf(f, "%d", &nr[i]);
index = 1;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
for(int k = 1; k <= N; k++)
{
n[index].i = nr[i];
n[index].j = nr[j];
n[index].k = nr[k];
n[index].sum = nr[i] + nr[j] + nr[k];
index++;
}
size = index - 1;
//mergeSort(n, 1, size);
for(int i = 1; i < size; i++)
for(int j = i+1; j <= size; j++)
if(n[i].sum > n[j].sum)
{
number aux = n[i];
n[i] = n[j];
n[j] = aux;
}
ok = 1;
for(int i = 1; i <= size; i++)
{
int sum = S - n[i].sum;
int a = 1;
int b = size;
for(;a<=b&&ok;)
{
int middle = (a+b) / 2;
if(n[middle].sum == sum)
{
fprintf(g, "%d %d %d %d %d %d", n[i].i, n[i].j, n[i].k, n[middle].i, n[middle].j, n[middle].k);
ok = 0;
}
if(n[middle].sum > sum)
b = middle - 1;
if(n[middle].sum < sum)
a = middle + 1;
}
}
if(ok)
fprintf(g, "-1");
fclose(f);
fclose(g);
return 0;
}