fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. double prob[2][100047];
  5. double sprob[100047];
  6.  
  7. int main() {
  8.     int N, M; cin >> N >> M;
  9.     if (M == 1) { cout << "1" << endl; return 0; }
  10.     vector<int> K(N);
  11.     int Krank = 0;
  12.     for (int &k:K) { cin >> k; Krank += k; }
  13.     prob[0][0] = 1;
  14.     for (int n=0; n<N; ++n) {
  15.         int prev=n&1, curr=1-prev;
  16.         sprob[0]=0;
  17.         for (int i=0; i<=Krank; ++i) sprob[i+1] = sprob[i] + prob[prev][i];
  18.         for (int i=0; i<=Krank; ++i) {
  19.             prob[curr][i] = sprob[i] - (i-M >= 0 ? sprob[i-M] : 0) - (i-K[n] >= 0 ? prob[prev][i-K[n]] : 0);
  20.             prob[curr][i] /= M-1;
  21.         }
  22.     }
  23.     double better = 0;
  24.     for (int i=1; i<Krank; ++i) better += prob[N&1][i];
  25.     better *= M-1;
  26.     cout << fixed << setprecision(15) << (better+1) << endl;
  27. }
Success #stdin #stdout 0s 5760KB
comments (?)
stdin
copy 
4 10
2
1
2
1
stdout
copy 
1.000000000000000
https://ideone.com/RAsfz6
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!