Cod sursa(job #2907651)

Utilizator sergi.uamSergiu Amzuloiu sergi.uam Data 30 mai 2022 23:22:25
Problema Dezastru Scor 10
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

int N, k;
int permutari = 0;
float suma = 0;
// PERMUTARI
typedef struct partialSolution
{
	float originalVector[25];
	float permutation[25];
	int position;
	int step;
} partialSolution;

int canReject(partialSolution PS)
{
	for (int i = 0; i < PS.step; i++)
	{
		if (PS.permutation[i] == PS.permutation[PS.step])
			return 1;
	}
	return 0;
}

int isSolution(partialSolution PS)
{
	return !canReject(PS) && PS.step == N - 1;
}

void printSolution(partialSolution PS)
{
	float p = 1;
	permutari++;
	for (int i = 0; i < k; i++)
		p = p * PS.permutation[i];
	suma = suma + p;
	
}

partialSolution increaseStep(partialSolution PS)
{
	PS.step++;
	PS.position = 0;
	return PS;
}

partialSolution getNextChoiceAtStep(partialSolution PS)
{
	PS.permutation[PS.step] = PS.originalVector[PS.position];
	PS.position++;
	return PS;
}

int hasChoiceAtStep(partialSolution PS)
{
	return PS.step < N && PS.position < N;
}

void backtracking(partialSolution PS)
{
	if (canReject(PS))
		return;
	if (isSolution(PS))
		printSolution(PS);
	PS = increaseStep(PS);
	while (hasChoiceAtStep(PS))
	{
		PS = getNextChoiceAtStep(PS);
		backtracking(PS);
	}
}

int main()
{
	partialSolution initialValues;

	FILE* in = fopen("dezastru.in", "r");
	fscanf(in, "%d %d", &N, &k);
	for (int i = 0; i < N; i++)
		fscanf(in, "%f", &initialValues.originalVector[i]);
	fclose(in);
	initialValues.position = -1;
	initialValues.step = -1;

	backtracking(initialValues);
	FILE* out = fopen("dezastru.out", "w");
	fprintf(out, "%6f", (float)suma/permutari);
	fclose(out);
	return 0;
}