Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * File: main.cpp
- * Author: Hrayr [HarHro94]
- * Problem: opencup
- * IDE: Visual C++ 2008
- */
- //#pragma comment(linker, "/STACK:66777216")
- #include <functional>
- #include <algorithm>
- #include <iostream>
- #include <cassert>
- #include <iomanip>
- #include <cstring>
- #include <cstdio>
- #include <string>
- #include <vector>
- #include <ctime>
- #include <queue>
- #include <stack>
- #include <cmath>
- #include <set>
- #include <map>
- using namespace std;
- #define pb push_back
- #define mp make_pair
- #define all(v) (v).begin(), (v).end()
- #define LL long long
- #define LD long double
- LD dp[100][100];
- int n, bad[100];
- int main()
- {
- #ifdef harhro94
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- double startTime = clock();
- #endif
- int i, j, k, u;
- cin >> n;
- for (i = 0; i < n; ++i)
- {
- cin >> bad[i];
- }
- for (i = 0; i < n; ++i)
- {
- for (j = 0; j < n; ++j)
- {
- LD busy = 0.0;
- LD free;
- for (k = 0; k < i; ++k)
- {
- busy += dp[k][j];
- }
- free = 1.0 - busy;
- if (i == j)
- {
- if (bad[i] == 0)
- {
- dp[i][j] = free;
- }
- else
- {
- dp[i][j] = free / (n - i);
- }
- }
- else
- {
- if (bad[i] == 0)
- {
- LD p = 0.0;
- for (k = 0; k < i; ++k)
- {
- LD tmp = 0.0;
- for (u = 0; u < i; ++u)
- {
- if (u == k)
- {
- continue;
- }
- tmp += dp[u][j];
- }
- tmp = 1.0 - tmp;
- p += tmp * dp[k][i];
- }
- dp[i][j] = p / (n - i);
- }
- else
- {
- dp[i][j] = free / (n - i);
- }
- }
- }
- cout << fixed << setprecision(10) << dp[i][i] << " ";
- }
- cout << endl;
- #ifdef harhro94
- double endTime = clock();
- printf("\nExecution time = %.3lf s", (endTime - startTime) / 1000.0);
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement