Cod sursa(job #2094195)

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

typedef unsigned int uint;

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

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

		uint 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(uint *stiva, uint nivel, FILE *out)
{
	uint i = 0;
	for(; i <= nivel; i++)
	{
		fprintf(out, "%u ", stiva[i]);
	}
	fprintf(out, "\n");
}

void backtrack(uint *stiva, uint nivel, uint n, uint cs, uint s, uint *vector, FILE *out)
{
	if(!FOUND && nivel < n)
	{
		uint 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(uint *vector, uint size)
{
	bool end = false;
	while(!end)
	{
		end = true;
		uint i = 0;
		for(; i < size - 1; i++)
		{
			if(vector[i] > vector[i + 1])
			{
				uint temp = vector[i];
				vector[i] = vector[i + 1];
				vector[i + 1] = temp;
				end = false;
			}
		}
	}
}