fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5.  
  6. int main() {
  7.     ios_base::sync_with_stdio(0);
  8.     cin.tie(0);
  9.     cout << fixed << setprecision(100);
  10.     int test_cases;
  11.     cin >> test_cases;
  12.     auto solve_costs = [&](vector<ll>& a, vector<ld>& cost) -> ld {
  13.         int n = (int) a.size();
  14.         vector<ld> pre(n);
  15.         for (int i = 0; i < n; i++) {
  16.             if (i == 0) {
  17.                 pre[i] = cost[i];
  18.             } else {
  19.                 pre[i] = pre[i - 1] + cost[i];
  20.             }
  21.         }
  22.         auto sum = [&](int l, int r) -> ld {
  23.             return pre[r] - (l == 0 ? 0 : pre[l - 1]);
  24.         };
  25.         vector<ld> mult(n);
  26.         for (int i = 0; i < (n + 1) / 2; i++) {
  27.             if (i == 0) {
  28.                 mult[i] = sum(0, n - 1);
  29.             } else {
  30.                 mult[i] = mult[i - 1] + sum(i, n - 1 - i);
  31.             }
  32.         }
  33.         for(int i = (n + 1) / 2; i < n; i++) {
  34.             mult[i] = mult[n - 1 - i];
  35.         }
  36.         for (int i = 0; i < n; i++) {
  37.             mult[i] -= cost[0];
  38.         }
  39.         ld ret = 0;
  40.         for (int i = 0; i < n; i++) {
  41.             ret += a[i] * mult[i];
  42.         }
  43.         return ret;
  44.     };
  45.     auto solve_case = [&](int tc) {
  46.         int n;
  47.         cin >> n;
  48.         vector<ll> a(n);
  49.         for (int i = 0; i < n; i++) {
  50.             cin >> a[i];
  51.         }
  52.         vector<ll> pre(n);
  53.         for (int i = 0; i < n; i++) {
  54.             if (i == 0) {
  55.                 pre[i] = a[i];
  56.             } else {
  57.                 pre[i] = pre[i - 1] + a[i];
  58.             }
  59.         }
  60.         auto small_choose = [&](ll x, ll y) -> ld {
  61.             if (y == 0) {
  62.                 return 1;
  63.             } else if (y == 1) {
  64.                 return x;
  65.             } else {
  66.                 return x * (x - 1) / 2;
  67.             }
  68.         };
  69.         auto sum = [&](int l, int r) -> ll {
  70.             return pre[r] - (l == 0 ? 0 : pre[l - 1]);
  71.         };
  72.         auto evaluate = [&](int l, int r) -> ld {
  73.             int bad = (l != 0) + (r != n - 1);
  74.             int good = r - l;
  75.             return sum(l, r) / small_choose(bad + good, bad);
  76.         };
  77.         ld ans = 0;
  78.         for (int r = 1; r < n; r++) {
  79.             ans += evaluate(0, r);
  80.         }
  81.         for (int l = 1; l < n - 1; l++) {
  82.             ans += evaluate(l, n - 1);
  83.         }
  84.         vector<ll> shrink(n - 2);
  85.         vector<ld> cost1(n - 2);
  86.         vector<ld> cost2(n - 2);
  87.         for (int i = 1; i < n - 1; i++) {
  88.             shrink[i - 1] = a[i];
  89.         }
  90.         for (int i = 1; i < n - 1; i++) {
  91.             cost1[i - 1] = ((ld) 1) / i;
  92.             cost2[i - 1] = ((ld) 1) / (i + 1);
  93.         }
  94.         ans += 2 * solve_costs(shrink, cost1);
  95.         ans -= 2 * solve_costs(shrink, cost2);
  96.         cout << ans << '\n';
  97.     };
  98.     for (int tc = 1; tc <= test_cases; tc++) {
  99.         cout << "Case #" << tc << ": ";
  100.         solve_case(tc);
  101.     }
  102. }
  103.  
Success #stdin #stdout 0s 4492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PUjYXC
language:
C++14 (gcc 8.3)
created:
3 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!