fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define sl(n) scanf("%lld", &n)
  6. #define for1(i, stop) for(ll i = 1; i <= stop; ++i)
  7. #define ms(n, i) memset(n, i, sizeof(n))
  8. #define pf printf
  9.  
  10. const ll sz = 110;
  11. ll a[sz], n;
  12. double dp[sz][3*sz];
  13. bool chk[sz][3*sz];
  14.  
  15. double solve(ll pos, ll c)
  16. {
  17.     double &ret = dp[pos][c];
  18.     if(chk[pos][c])
  19.         return ret;
  20.  
  21.     chk[pos][c] = 1, ret = (pos != 0);
  22.     int cnt = 0, nxt = c-a[pos], l = n+1, r = pos;
  23.  
  24.     for(int i = pos+1; i <= n; ++i) {
  25.         if(a[i] > nxt) break;
  26.  
  27.         if(a[i] > a[pos]) {
  28.             if(l==n+1) l = i;
  29.             r = i;
  30.             cnt++;
  31.         }
  32.     }
  33.  
  34.     for(int i = l; i <= r; i++)
  35.         ret += (double)1/cnt * solve(i, nxt);
  36.  
  37.     return ret;
  38. }
  39.  
  40. int main()
  41. {
  42.     ll t;
  43.     cin >> t;
  44.  
  45.     while(t--) {
  46.         ll c;
  47.         sl(n), sl(c);
  48.  
  49.         for1(i, n) sl(a[i]);
  50.         sort(a+1, a+n+1);
  51.  
  52.         ms(chk, 0);
  53.         pf("%0.9f\n", solve(0, c));
  54.     }
  55.  
  56.     return 0;
  57. }
  58.  
  59.  
Success #stdin #stdout 0s 5672KB
comments (?)
stdin
copy 
2
3 10
10 3 6
2 5
5 5
stdout
copy 
1.333333333
1.000000000
https://ideone.com/9eZgDh
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!