fork download
copy 
  1. #include<iostream>
  2. #include<iomanip>
  3. #include<limits>
  4. #include<cmath>
  5. using namespace std;
  6. int main(){
  7.     int t;
  8.     cin>>t;
  9.     while(t--){
  10.     	int n,c,k,i,x,y,limit=0,j,f,e;   
  11.  
  12. 		cin>>n>>c>>k;
  13.  
  14. 		int noe[n],fnoe[k+1],s=k;
  15.  
  16. 		for(i=0;i<n;i++){
  17. 			noe[i]=0;
  18. 		}
  19.  
  20.                                                               //noe will be used to store
  21.                                                               //the no. of occurences of
  22.                                                               //each integer from 1 to n.
  23. 		while(s--){
  24. 			cin>>x>>y;
  25. 			for(i=(x-1);i<y;i++)
  26. 			   noe[i]++;                     
  27.  
  28. 		}
  29.  
  30.  
  31.  
  32.  
  33. 		long double pin[c],pin2[c],pin3[c];
  34. 		                                             //for the first occurence of a particular 
  35. 		                                             //integer
  36. 		for(i=0;i<c;i++){
  37. 			pin[i]=0.5*(1.0/double(c));             //probability that the subset won't be
  38. 			                                         //empty=0.5
  39. 			                                        //multiplied by probabilty of a particular 
  40. 			                                        //colour to be selected. 
  41. 			                                       //this is applicable for all colours except 1
  42.  
  43.  
  44. 		}
  45. 		pin[1]=0.5*(1.0/double(c))+0.5;            //for colour 1: probabability that the subset
  46. 		                                           //will be empty will also be added to 0.5*(1/c)
  47.  
  48.  
  49.  
  50. 		long double ans[k],out=0;
  51.  
  52.         for(i=0;i<=k;i++)
  53.              ans[i]=0;                             //suppose the no. of occurences of a particular
  54.                                                    //integer is x then the expected colour 
  55.                                                    //is ans[x]
  56.  
  57.         ans[0]=1;
  58.                                                    //for the first occurence calculating the 
  59.                                                    //expected value of the colour
  60.  
  61. 		for(i=0;i<c;i++){                                      
  62. 	    	ans[1]=double(ans[1])+double(pin[i])*double(i);   
  63. 	    	pin2[i]=pin[i];
  64. 		}
  65.                                                    //now for each subsequent occurence
  66.                                                    // calculating ans
  67.  
  68. 		for(i=2;i<=k;i++){
  69.  
  70.             for(e=0;e<c;e++)
  71.                   pin3[e]=0;
  72.  
  73. 			for(j=0;j<c;j++){
  74.  
  75. 				for(f=0;f<c;f++){
  76.  
  77. 					pin3[(j*f)%c]=double(pin3[(j*f)%c])+double(pin[j])*double(pin2[f]);
  78. 				}
  79. 			}
  80.  
  81. 			for(s=0;s<c;s++){
  82. 				ans[i]=double(ans[i])+double(pin3[s])*double(s);
  83.                 pin2[s]=double(pin3[s]);
  84. 			}
  85. 		}
  86.  
  87.     ans[0]=1;                             //if an integer has zero occurences ans is 1
  88.  
  89.  
  90.  
  91. 		for(i=0;i<n;i++){
  92. 			out=double(out)+double(ans[noe[i]]);              
  93.  
  94. 		}
  95. 		 std::cout <<std::setprecision(10) << out << "\n";
  96. 	}
  97.     return 0;
  98. }  
  99.  
Success #stdin #stdout 0s 3300KB
comments (?)
stdin
copy 
2
4 3 4
1 2
2 4
3 3
1 4
7 10 7
7 7
3 4
1 2
5 5
4 5
2 7
3 3
stdout
copy 
3.444444444
22.943125
https://ideone.com/qsQFll
language:
C++ (gcc 8.3)
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!