Submission #295766

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

using namespace std;
double prob[128][256][128];
// already,last, n-th
int main(void)
{
  int n,k;
  cin >> n >> k;
  REP(already,n+1) REP(last,k+1) REP(i,n+1) prob[already][last][i]=0.0;
  double p;
  cin >> p;
  prob[1][1][1]=1.0;
  FOR(i,1,n){
    cin >> p;
    p/=100;
    REP(already,n+1) REP(last,k+1){
      if(already<last)
	prob[already+1][last][i+1]+=prob[already][last][i]*p;
      else if(already<k)
	prob[already+1][last+1][i+1]+=prob[already][last][i]*p;
      else
	prob[already][last][i+1]+=prob[already][last][i]*p;
      if(last+1<k)
	prob[already+1][last+2][i+1]+=prob[already][last][i]*(1-p);
      else
	prob[already][last][i+1]+=prob[already][last][i]*(1-p);
    }
  }
  double exp=0.0;
  REP(already,n+1) REP(last,k+1) exp+=prob[already][last][n]*already;
  cout << fixed << setprecision(10) << k-exp << endl;    
  return 0;
}

Submission Info

Judge Result