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 rep1(i, start) for(ll i = start; i >= 1; --i)
  8. #define pf printf
  9.  
  10. const ll sz = 1e4 + 10;
  11. ll a[sz], cnt[sz];
  12. double dp[sz];
  13.  
  14. int main()
  15. {
  16.     ll t;
  17.     cin >> t;
  18.  
  19.     while(t--) {
  20.         ll n, c;
  21.         sl(n), sl(c);
  22.  
  23.         for1(i, n) sl(a[i]);
  24.         sort(a+1, a+n+1);
  25.  
  26.         for(ll i = 0; i <= c; i++) dp[i] = cnt[i] = 0;
  27.  
  28.         rep1(i, n) {
  29.  
  30.             ll l = i;
  31.             for(ll j = i; j >= 1; j--) {
  32.                 if(a[j] != a[i])
  33.                     break;
  34.  
  35.                 l = j;
  36.             }
  37.             ll tot = i-l+1;
  38.  
  39.             for(ll x = c; x >= a[i]; x--) {
  40.                 ll nxt = x-a[i];
  41.  
  42.                 if(cnt[nxt] == 0)
  43.                     dp[x] += tot;
  44.                 else
  45.                     dp[x] += (tot + tot*(double)1/cnt[nxt] * dp[nxt]);
  46.  
  47.                 cnt[x] += (i-l+1);
  48.             }
  49.  
  50.             i = l;
  51.         }
  52.  
  53.         pf("%0.9f\n", (double)1/n*dp[c]);
  54.     }
  55.  
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0.01s 5536KB
comments (?)
stdin
copy 
2
3 10
10 3 6
2 5
5 5
stdout
copy 
1.333333333
1.000000000
https://ideone.com/Nog7Jm
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!