Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define llong long long
- using namespace std;
- typedef vector<int> big;
- const int MAXN = (int) 5e3 + 7;
- const int INF = (int) 2e9 + 7;
- int t, n;
- long long path[MAXN][MAXN];
- double prob[MAXN][MAXN];
- double expect[MAXN][MAXN];
- int main() {
- #ifdef LOCAL
- freopen("in", "r", stdin);
- #endif
- ios_base::sync_with_stdio(0);
- cin >> t;
- while (t--) {
- cin >> n;
- for (int i = 1; i <= n + 1; i++) {
- for (int j = 1; j <= n + 1; j++) {
- prob[i][j] = 0.0;
- expect[i][j] = 0.0;
- }
- }
- prob[1][1] = 1.0;
- expect[1][1] = 0.0;
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= i; j++) {
- int d, dr;
- cin >> d >> dr;
- if (d < dr) {
- prob[i + 1][j] += prob[i][j];
- expect[i + 1][j] += expect[i][j] + prob[i][j] * d;
- }
- else if (dr < d) {
- prob[i + 1][j + 1] += prob[i][j];
- expect[i + 1][j + 1] += expect[i][j] + prob[i][j] * dr;
- }
- else {
- double cur = expect[i][j] + prob[i][j] * d;
- cur /= 2;
- prob[i + 1][j] += prob[i][j] * 0.5;
- prob[i + 1][j + 1] += prob[i][j] * 0.5;
- expect[i + 1][j] += cur;
- expect[i + 1][j + 1] += cur;
- }
- }
- }
- double ans = 0.0;
- for (int i = 1; i <= n + 1; i++) {
- ans += expect[n + 1][i];
- }
- cout << fixed << setprecision(10) << ans << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement