Cod sursa(job #2094197)

Utilizator arcoC. Nicolae arco Data 25 decembrie 2017 12:27:50
Problema Loto Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>

bool FOUND = false;
void bubble_sort(uint64_t *vector, uint64_t size);
void backtrack(uint64_t *stiva, uint64_t nivel, uint64_t n, uint64_t cs, uint64_t s, uint64_t *vector, FILE *out);
void tipar(uint64_t *stiva, uint64_t nivel, FILE *out);

int main(void)
{
	FILE *in = fopen("loto.in", "r");
	FILE *out = fopen("loto.out", "w");
	if(in != NULL && out != NULL)
	{
		uint64_t n, s, vector[110];
		fscanf(in, "%llu%*c%llu%*c", &n, &s);
		uint64_t i = 0;
		for(; i < n; i++)
		{
			uint64_t t;
			fscanf(in, "%llu%*c", &t);
			vector[i] = t;
		}
		bubble_sort(vector, n);

		uint64_t stiva[110];
		backtrack(stiva, 0, 6, 0, s, vector, out);

		if(!FOUND)
		{
			fprintf(out, "-1\n");
		}

		fclose(in);
		fclose(out);
	}
	else
	{
		printf("Error\n");
	}

	return 0;
}

void tipar(uint64_t *stiva, uint64_t nivel, FILE *out)
{
	uint64_t i = 0;
	for(; i <= nivel; i++)
	{
		fprintf(out, "%llu ", stiva[i]);
	}
	fprintf(out, "\n");
}

void backtrack(uint64_t *stiva, uint64_t nivel, uint64_t n, uint64_t cs, uint64_t s, uint64_t *vector, FILE *out)
{
	if(!FOUND && nivel < n)
	{
		uint64_t i = 0;
		for(; i < n; i++)
		{
			if((cs + vector[i]) <= s)
			{
				stiva[nivel] = vector[i];
				if(nivel == (n - 1) && (cs + vector[i]) == s)
				{
					tipar(stiva, nivel, out);
					FOUND = true;
					break;
				}
				else
				{
					backtrack(stiva, nivel + 1, n, cs + vector[i], s, vector, out);
				}
			}
		}
	}
}

void bubble_sort(uint64_t *vector, uint64_t size)
{
	bool end = false;
	while(!end)
	{
		end = true;
		uint64_t i = 0;
		for(; i < size - 1; i++)
		{
			if(vector[i] > vector[i + 1])
			{
				uint64_t temp = vector[i];
				vector[i] = vector[i + 1];
				vector[i + 1] = temp;
				end = false;
			}
		}
	}
}