fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <cstdio>
  4. using namespace std;
  5.  
  6. #define maxn 41
  7. long long dp1[maxn][maxn];
  8. int dp2[maxn][maxn];
  9. int colors[maxn];
  10. unsigned long long cost[maxn];
  11. unsigned long long one = 1LL;
  12.  
  13. int main() {
  14.     int t;
  15.     cin >> t;
  16.     while(t--) {
  17.         map<int,int> mapping;
  18.         int n, m, ci, color=0;
  19.         long long pi;
  20.         cin >> n >> m;
  21.         for(int i=0;i<=n;++i) {
  22.             colors[i] = 0;
  23.             cost[i] = 0;
  24.             dp1[0][i] = 0;
  25.             dp1[i][0] = 0;
  26.             dp2[0][i] = 0;
  27.             dp2[i][0] = 1;
  28.         }
  29.         color = 0;
  30.         for(int i=0;i<n;++i) {
  31.             cin >> ci >> pi;
  32.             int j;
  33.             if(!mapping[ci]) {
  34.                 mapping[ci] = ++color;
  35.                 j = color;
  36.             } else j = mapping[ci];
  37.             ++colors[j];
  38.             cost[j] += pi;
  39.         }
  40.  
  41.         // denominator
  42.         for(int i=1;i<=color;++i) {
  43.             for(int j=1;j<=color;++j) {
  44.                 dp2[i][j] = dp2[i-1][j] + dp2[i-1][j-1]*((one<<colors[i])-1);
  45.             }
  46.         }
  47.  
  48.         // numerator
  49.         for(int i=1;i<=color;++i) {
  50.             for(int j=1;j<=color;++j) {
  51.                 dp1[i][j] = dp1[i-1][j] +
  52.                             dp1[i-1][j-1]*((one<<colors[i])-1) +
  53.                             dp2[i-1][j-1]*cost[i]*(one<<(colors[i]-1));
  54.             }
  55.         }
  56.  
  57.         unsigned long long num=0, den=0;
  58.  
  59.         for(int i=m;i<=color;++i) {
  60.             num += dp1[color][i];
  61.             den += dp2[color][i];
  62.         }
  63.         den = max(den,one);
  64.         double res = (double)num/(double)den;
  65.         printf("%.6lf\n",res);
  66.     }
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0s 2888KB
comments (?)
stdin
copy 
8
3 0
1 1
2 2
3 3
3 1
1 1
2 2
3 3
3 2
1 1
2 2
3 3
3 3
1 1
2 2
3 3
6 0
1 2 
2 3
2 4
3 5
3 6
3 7
6 1
1 2 
2 3
2 4
3 5
3 6
3 7
6 2
1 2 
2 3
2 4
3 5
3 6
3 7
6 3
1 2 
2 3
2 4
3 5
3 6
3 7
stdout
copy 
3.000000
3.428571
4.500000
6.000000
13.500000
13.714286
14.923077
16.952381
https://ideone.com/V5FmHz
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!