fork(3) download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<vector>
  4. #include<cstring>
  5. #include<algorithm>
  6. #include<set>
  7. #include<queue>
  8. #include<cmath>
  9. #include<bitset>
  10. #include<map>
  11. #define test(t) while(t--)
  12. #define cin(n) scanf("%d",&n)
  13. #define cinl(n) scanf("%lld",&n)
  14.  
  15. #define cout(n) printf("%d\n",n)
  16. #define rep(i,a,n) for(i=a;i<=n;i++)
  17. #define vi vector<int>
  18. #define vii vector< vector<int> >
  19. #define vpii vector< pair<int,int> >
  20. #define mii map<int,int>
  21. #define eps 1e-12
  22. #define pb push_back
  23. #define mp make_pair
  24. #define imax (int) 1000000007
  25. #define ill long long
  26. #define gc getchar_unlocked
  27. #include<stack>
  28. using namespace std;
  29. #define mod 1000000007
  30. #define inf 10000000
  31. #include <cstdio>
  32. #include <algorithm>
  33.  
  34. using namespace std;
  35.  
  36. ill powe(int aa,int b)
  37. {
  38.     ill ans=1;
  39.     ill a=aa*1LL;
  40.     while(b)
  41.     {
  42.         if(b&1)
  43.             ans=(ans*1LL*a)%mod;
  44.         a=(a*1LL*a)%mod;
  45.         b=b/2;
  46.     }
  47.     return ans;
  48. }
  49. ill modinv(int a)
  50. {
  51.     return powe(a,mod-2);
  52. }
  53. #define eps 1e-12
  54. #define gc getchar_unlocked
  55. /*
  56.  
  57. int gcd(int i,int j)
  58. {
  59.     if(j==0)
  60.         return i;
  61.  
  62.     return gcd(j,i%j);
  63. }
  64.  
  65. #define MAX 100000001
  66. int a[100000009]={0};
  67. vector<int>v;
  68. int sieve()
  69. {
  70.     int i,p,n;
  71.  
  72.     for(i=2;i<=MAX;i+=2)
  73.         a[i]=2;
  74.     for(i=3;i<=MAX;i+=3)
  75.     {
  76.        if(a[i]==0)
  77.         a[i]=3;
  78.        }
  79.     for(i=5;i*i<=MAX;)
  80.     {
  81.         if(a[i]==0)
  82.         {
  83.             //v.pb(i);
  84.             a[i]=i;
  85.         }
  86.         for(p=i*i;p<=MAX;p+=2*i)
  87.         {
  88.             if(a[p]==0)
  89.             a[p]=i;
  90.         }
  91.         if(i%6==1)
  92.             i+=4;
  93.         else
  94.             i+=2;
  95.     }
  96.  
  97.     for(i=10000;i<=MAX;i++)
  98.     {
  99.        if(a[i]==0)
  100.        {
  101.            a[i]=i;
  102.        }
  103.     }
  104.     return 0;
  105. }
  106. */
  107. double dp[45][45],dp2[45][45];
  108. vector<int>v,s;
  109. int m,n;
  110. ill sum[45];
  111. double sub(int pos,int coun)
  112. {
  113.     if(dp2[pos][coun]!=-1)
  114.         return dp2[pos][coun];
  115.  
  116.  
  117.     if(pos==v.size())
  118.     {
  119.         if(coun>=m)
  120.             return dp2[pos][coun]=1;
  121.         return dp2[pos][coun]=0;
  122.     }
  123.  
  124.     double ret=0;
  125.  
  126.  
  127.     double val=(powe(2,v[pos])-1)*1.0*sub(pos+1,coun+1);
  128.     ret=ret+val;
  129.  
  130.     ret=ret+sub(pos+1,coun);
  131.  
  132.     //cout<<pos<<" "<<coun<<" "<<val<<"\n";
  133.     return dp2[pos][coun]=ret;
  134. }
  135.  
  136.  double rec(int pos,int coun)
  137. {
  138.     if(dp[pos][coun]!=-1)
  139.         return dp[pos][coun];
  140.  
  141.     if(pos==v.size())
  142.         return 0;
  143.  
  144.     double ret=0;
  145.  
  146.     ret=ret+rec(pos+1,coun);
  147.  
  148.     double val=(powe(2,v[pos]-1)*1.0*s[pos]);
  149.  
  150.     ret=ret+val*(dp2[pos+1][coun+1])+rec(pos+1,coun+1);
  151.  
  152.  
  153.     return dp[pos][coun]=ret;
  154. }
  155.  
  156. int main()
  157. {
  158.     int t,i,j,k,l;
  159.     cin(t);
  160.  
  161.     while(t--)
  162.     {
  163.         cin(n);
  164.         cin(m);
  165.         v.clear();
  166.         for(i=0;i<=40;i++)
  167.         {
  168.             for(j=0;j<=40;j++)
  169.             {
  170.                 dp[i][j]=dp2[i][j]=-1;
  171.             }
  172.         }
  173.  
  174.         memset(sum,0,sizeof(sum));
  175.         s.clear();
  176.         for(i=0;i<n;i++)
  177.         {
  178.             cin(j);
  179.             cin(k);
  180.             v.pb(j);
  181.             sum[j]+=k;
  182.         }
  183.         vector<int>z;z.clear();
  184.         sort(v.begin(),v.end());
  185.  
  186.         int c=1;
  187.         for(i=0;i<n;i++)
  188.         {
  189.             if(!i)
  190.                 continue;
  191.  
  192.             if(v[i]==v[i-1])
  193.             {
  194.                 c++;
  195.             }
  196.             else
  197.             {
  198.                 z.pb(c);
  199.                 s.pb(sum[v[i-1]]);
  200.                 c=1;
  201.             }
  202.         }
  203.  
  204.             z.pb(c);
  205.             s.pb(sum[v[n-1]]);
  206.  
  207.  
  208.         v=z;
  209.         double den=1;
  210.  
  211.         double  sum=0;
  212.  
  213.         sub(0,0);
  214.         rec(0,0);
  215.         sum=dp[0][0];
  216.         den=dp2[0][0];
  217.  
  218.         //cout<<sum<<"\n";
  219.         //cout<<den<<"\n";
  220.  
  221.         double ans=(sum*1.0)/(den*1.0);
  222.         //cout<<dp2[2][1]<<"\n";
  223.         //cout<<v[0]<<" "<<v[1]<<"\n";
  224.         if(den==0)
  225.             ans=0;
  226.         printf("%.7lf\n",ans);
  227.     }
  228.     return 0;
  229. }
  230.  
Success #stdin #stdout 0s 3512KB
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.0000000
3.4285714
4.5000000
6.0000000
9.0000000
9.1428571
9.3846154
10.0952381
https://ideone.com/twTBDH
input created from http://i...content-available-to-author-only...e.com/rPnqVX
language:
C++ (gcc 8.3)
created:
10 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!