Advertisement
Guest User

Untitled

a guest
Mar 3rd, 2013
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.45 KB | None | 0 0
  1. /*
  2.  * File:    main.cpp
  3.  * Author:  Hrayr [HarHro94]
  4.  * Problem: opencup
  5.  * IDE:     Visual C++ 2008
  6.  */
  7. //#pragma comment(linker, "/STACK:66777216")
  8. #include <functional>
  9. #include <algorithm>
  10. #include <iostream>
  11. #include <cassert>
  12. #include <iomanip>
  13. #include <cstring>
  14. #include <cstdio>
  15. #include <string>
  16. #include <vector>
  17. #include <ctime>
  18. #include <queue>
  19. #include <stack>
  20. #include <cmath>
  21. #include <set>
  22. #include <map>
  23. using namespace std;
  24.  
  25. #define pb push_back
  26. #define mp make_pair
  27. #define all(v) (v).begin(), (v).end()
  28. #define LL long long
  29. #define LD long double
  30.  
  31. LD dp[100][100];
  32. int n, bad[100];
  33.  
  34. int main()
  35. {
  36. #ifdef harhro94
  37.     freopen("input.txt", "r", stdin);
  38.     freopen("output.txt", "w", stdout);
  39.     double startTime = clock();
  40. #endif
  41.  
  42.     int i, j, k, u;
  43.     cin >> n;
  44.     for (i = 0; i < n; ++i)
  45.     {
  46.         cin >> bad[i];
  47.     }
  48.     for (i = 0; i < n; ++i)
  49.     {
  50.         for (j = 0; j < n; ++j)
  51.         {
  52.             LD busy = 0.0;
  53.             LD free;
  54.             for (k = 0; k < i; ++k)
  55.             {
  56.                 busy += dp[k][j];
  57.             }
  58.             free = 1.0 - busy;
  59.             if (i == j)
  60.             {
  61.                 if (bad[i] == 0)
  62.                 {
  63.                     dp[i][j] = free;
  64.                 }
  65.                 else
  66.                 {
  67.                     dp[i][j] = free / (n - i);
  68.                 }
  69.             }
  70.             else
  71.             {
  72.                 if (bad[i] == 0)
  73.                 {
  74.                     LD p = 0.0;
  75.                     for (k = 0; k < i; ++k)
  76.                     {
  77.                         LD tmp = 0.0;
  78.                         for (u = 0; u < i; ++u)
  79.                         {
  80.                             if (u == k)
  81.                             {
  82.                                 continue;
  83.                             }
  84.                             tmp += dp[u][j];
  85.                         }
  86.                         tmp = 1.0 - tmp;
  87.                         p += tmp * dp[k][i];
  88.                     }
  89.                     dp[i][j] = p / (n - i);
  90.                 }
  91.                 else
  92.                 {
  93.                     dp[i][j] = free / (n - i);
  94.                 }
  95.             }
  96.         }
  97.         cout << fixed << setprecision(10) << dp[i][i] << " ";
  98.     }
  99.     cout << endl;
  100.  
  101. #ifdef harhro94
  102.     double endTime = clock();
  103.     printf("\nExecution time = %.3lf s", (endTime - startTime) / 1000.0);
  104. #endif
  105.  
  106.     return 0;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement