fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int b,t;
  6. double ff;
  7. double prob[12];
  8. double val[12];
  9.  
  10. double f(int idx, int mask)
  11. {
  12.     if ( idx == t ) return 0.0;
  13.     if ( mask == ((1<<b)-1) ) return 0.0;
  14.     double p = -1.0;
  15.     int ii = -1;
  16.     for ( int i = 0; i < b; i++ ) {
  17.         if ( mask&(1<<i)) continue;
  18.         if ( prob[i]*val[i] > p ) {
  19.             p = prob[i]*val[i];
  20.             ii = i;
  21.         }
  22.     }
  23.     double ans = 0.0,now=prob[ii];
  24.     // not solve
  25.     prob[ii] *= ff;
  26.     ans += (1.0-now)*f(idx+1,mask);
  27.    // solve
  28.     prob[ii] /= ff;
  29.     ans += now*(val[ii] + f(idx+1,mask|(1<<ii)));
  30.     return ans;
  31. }
  32.  
  33. int main()
  34. {
  35.     cin >> b >> t >> ff;
  36.     for ( int i = 0; i < b; i++ ) cin >> prob[i] >> val[i];
  37.     double ans = f(0,0);
  38.     printf("%0.6lf\n", ans);
  39.     return 0;
  40. }
Success #stdin #stdout 0s 2732KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.000000
https://ideone.com/8h8X4v
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 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!