fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long double dp[6005], ndp[6005];
  5.  
  6. class BeatTheStar {
  7. 	public:
  8. 	double doesItMatter( int n, int g ) 
  9. 	{
  10. 		long long sum = n*(n+1)/2;
  11.  
  12. 		for(int j=0;j<6005;j++)
  13. 			dp[j] = ndp[j] = 0;
  14.  
  15. 		dp[0] = 1;
  16. 		for(int num=1;num<=n;num++)
  17. 		{
  18. 			// only consider elements other than g
  19. 			if( num == g )
  20. 				continue;
  21.  
  22. 			// transitions ( knapsack )
  23. 			for(int s=0;s+num<=sum;s++)
  24. 			{
  25. 				// don't take num
  26. 				ndp[s] += 0.5*dp[s];
  27.  
  28. 				// take num
  29. 				ndp[num+s] += 0.5*dp[s];
  30. 			}
  31.  
  32. 			// copy new layer to old layer, and reset new layer
  33. 			for(int j=0;j<6005;j++)
  34. 			{
  35. 				dp[j] = ndp[j];
  36. 				ndp[j] = 0;
  37. 			}
  38. 		}
  39.  
  40. 		long double ans = 0;
  41. 		for(int s=0;s<=sum;s++)
  42. 		{
  43. 			// if s is the sum of a good subset
  44. 			if( 2*s < sum && 2*(s + g) > sum )
  45. 			{
  46. 				// add probability of making s, without using g
  47. 				ans += dp[s];
  48. 			}
  49. 		}
  50.  
  51. 		return ans;
  52. 	}
  53. };
  54.  
  55. int main()
  56. {
  57. 	BeatTheStar b;
  58.  
  59. 	int test;
  60. 	cin>>test;
  61. 	for(int i=0;i<test;i++)
  62. 	{
  63. 		int n,g;
  64. 		cin>>n>>g;
  65. 		cout<<fixed<<setprecision(4)<<b.doesItMatter(n,g)<<"\n";
  66. 	}
  67.  
  68. 	return 0;
  69. }
Success #stdin #stdout 0.01s 4196KB
comments (?)
stdin 
6
2 1
5 5
5 1
5 2
9 7
98 98
stdout 
0.0000
0.6250
0.1250
0.1250
0.3281
0.1393
https://ideone.com/J5JeEf
language:
C++14 (gcc 8.3)
created:
4 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!