Mai intai trebuie sa te autentifici.
Cod sursa(job #2096540)
Utilizator | Data | 29 decembrie 2017 13:29:22 | |
---|---|---|---|
Problema | Dezastru | Scor | 0 |
Compilator | c | Status | done |
Runda | Arhiva de probleme | Marime | 1.66 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);
fprintf(out, "%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);
}
}
}
}