Cod sursa(job #2096538)

Utilizator arcoC. Nicolae arco Data 29 decembrie 2017 13:28:57
Problema Dezastru Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>

typedef unsigned int uint;

void backtrack(uint *stiva, uint nivel, double *vector, uint n, uint k);
bool valid(uint *stiva, uint nivel, uint last);
void tipar(uint *stiva, uint nivel);

double prob = 0.0;

int main(void)
{
	FILE *in = fopen("dezastru.in", "r");
	FILE *out = fopen("dezastru.out", "w");
	if(in != NULL && out != NULL)
	{
		uint n, k;
		fscanf(in, "%u%*c%u%*c", &n, &k);

		double vector[30];
		uint i = 0;
		for(; i < n; i++)
		{
			double t;
			fscanf(in, "%lf%*c", &t);
			vector[i] = t;
		}
		uint64_t f = 1;
		i = 2;
		for(; i <= n; i++)
		{
			f *= i;
		}

		uint stiva[30];
		backtrack(stiva, 0, vector, n, k);

		printf("%lf\n", prob / (double)f);

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

	return 0;
}

void tipar(uint *stiva, uint nivel)
{
	uint i = 0;
	for(; i <= nivel; i++)
	{
		printf("%u ", stiva[i]);
	}
	printf("\n");
}

bool valid(uint *stiva, uint nivel, uint last)
{
	uint i = 0;
	for(; i < nivel; i++)
	{
		if(stiva[i] >= last)
		{
			return false;
		}
	}

	return true;
}

void backtrack(uint *stiva, uint nivel, double *vector, uint n, uint k)
{
	uint i = (nivel > 0) ? stiva[nivel - 1] + 1 : 1;
	for(; i <= n; i++)
	{
		stiva[nivel] = i;
		if(valid(stiva, nivel, i))
		{
			if(nivel == (k - 1))
			{
				double p = vector[stiva[0] - 1];
				uint j = 1;
				for(; j <= nivel; j++)
				{
					p *= vector[stiva[j] - 1];
				}
				prob += p * 2;
			}
			else
			{
				backtrack(stiva, nivel + 1, vector, n, k);
			}
		}
	}
}