Advertisement
Guest User

problem FFFFFUUUUUU

a guest
May 7th, 2012
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstdio>
  4. #include <iomanip>
  5. #include <sstream>
  6. #include <cstring>
  7. #include <string>
  8. #include <cmath>
  9. #include <stack>
  10. #include <list>
  11. #include <queue>
  12. #include <deque>
  13. #include <set>
  14. #include <map>
  15. #include <vector>
  16. #include <algorithm>
  17. #include <numeric>
  18. #include <utility>
  19. #include <functional>
  20. #include <limits>
  21. using namespace std;
  22.  
  23. typedef long long ll;
  24. typedef unsigned long long ull;
  25. typedef unsigned int ui;
  26.  
  27. const double pi = acos(-1.0);
  28.  
  29. #define oned(a, x1, x2) { cout << #a << ":"; for(int _i = (x1); _i < (x2); _i++){ cout << " " << a[_i]; } cout << endl; }
  30. #define twod(a, x1, x2, y1, y2) { cout << #a << ":" << endl; for(int _i = (x1); _i < (x2); _i++){ for(int _j = (y1); _j < (y2); _j++){ cout << (_j > y1 ? " " : "") << a[_i][_j]; } cout << endl; } }
  31. #define mp(x, y) make_pair(x, y)
  32.  
  33. int n, m;
  34. double dp[1000005], psum[1000005];
  35.  
  36. void solve() {
  37.     for(int i = n; i <= n*m; i++) {
  38.         dp[i] = i*1./n;
  39.     }
  40.    
  41.     for(int k = n-1; k > 0; k--) {
  42.         for(int i = 0; i < n*m; i++) {
  43.             psum[i+1] = dp[i+1]+psum[i];
  44.         }
  45.        
  46.         double ik = 1./k, im = 1./m;
  47.         for(int i = k; i <= n*m; i++) {
  48.             dp[i] = max(i*ik, (psum[min(n*m,i+m)]-psum[i])*im);
  49.         }
  50.     }
  51.    
  52.     double res = 0;
  53.     for(int i = 1; i <= m; i++) {
  54.         res += dp[i];
  55.     }
  56.     cout << fixed << setprecision(12);
  57.     cout << res / m << endl;
  58. }
  59.  
  60. int main() {
  61. //  freopen("F.in", "r", stdin);
  62.     while(cin >> n >> m) {
  63.         solve();
  64.     }
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement