Cod sursa(job #491213)

Utilizator cristian9Cristian Zloteanu cristian9 Data 10 octombrie 2010 18:41:13
Problema Dezastru Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
/*#include<stdio.h>

int p, v[30], aa, n;
double st[26], sum;

void back(int k){
    int i;
    double s=1;
    if(k==p){
        for(i=1; i<=p; i++){
            s*=st[v[i]];
        }
        sum+=s;
        s=1;
        aa++;
    }
    else{
        for(i=v[k]+1; i<=n; i++){
            v[k+1]=i;
            back(k+1);
        }
    }
}

int main(){
    freopen ("dezastru.in", "r", stdin);
    freopen ("dezastru.out", "w", stdout);

    int i;

    scanf("%d %d", &n, &p);

    if(!p){
        printf("100");
        return 0;
    }

    for(i=1; i<=n; i++)
        scanf("%lf", &st[i]);

    back(0);

    printf("%6lf ", sum/aa);

    return 0;
}*/

#include<stdio.h>

int n,st[100], k, p, aa;
double v[30], s;

void  Init (){
    if (k > 1)
        st[k] = st[k-1];
    else
        st[k] = 0;
}

int evalid(){
	int i;
	for(i=1; i<k; i++){
		if(st[k]==st[i]){
			return 0;
		}
	}
	return 1;
}

int succesor(){
	if(st[k]<n-p+k){
		st[k]++;
		return 1;
	}
	return 0;
}

void afisare(){
	int i;
	double P=1;
	for(i=1; i<=p; i++){
		//printf("%lf ", v[st[i]]);
		P*=v[st[i]];
	}
	s+=P;
	//printf("%lf\n", P);
	aa++;
}

int solutie(){
	if(k==p){
		return 1;
	}
	return 0;
}

void back()
{
	int as;
	k=1;
	st[k]=0;
	while(k>0){
		do{} while((as=succesor()) && !evalid());
		if(as){
			if(solutie()){
				afisare();
			}
			else{
				k++;
				Init();
			}
		}
		else{
			k--;
		}
	}
}

int main()
{
	freopen ("dezastru.in", "r", stdin);
	freopen ("dezastru.out", "w", stdout);

	int i;
	scanf("%d %d", &n, &p);
if(p==0){ printf("100");
return 0;
}
	for(i=1; i<=n; i++)
        scanf("%lf ", &v[i]);

	back();
	printf("%6lf", s/aa);
	return 0;
}