fork(2) download
copy 
  1.  
  2. #include <iostream>
  3. #include <fstream>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <vector>
  9. #include <math.h>
  10.  
  11. using namespace std;
  12.  
  13. typedef long long LL;
  14. typedef vector<int> vi;
  15.  
  16. const int B = 10;
  17. const int T = 107;
  18.  
  19. map<int, double> dp[1 << B][T];
  20.  
  21. struct S
  22. {
  23. 	double s;
  24. 	double p;
  25. 	int mask;
  26.  
  27. 	bool operator < (const S& rhs) const
  28. 	{
  29. 		return s * p > rhs.s * rhs.p;
  30. 	}
  31. };
  32.  
  33. vector<S> v;
  34.  
  35. int t;
  36.  
  37. double D(int mask, int pos, int k)
  38. {
  39. 	if (pos == v.size() || k == t)
  40. 		return 0;
  41.  
  42. 	if (mask & v[pos].mask)
  43. 		return D(mask, pos + 1, k);
  44.  
  45. 	double& res = dp[mask][pos][k];
  46. 	if (res > 1)
  47. 		return res - 2;
  48.  
  49. 	res = 2;
  50.  
  51. 	res += v[pos].p * (v[pos].s + D(mask | v[pos].mask, pos + 1, k + 1));
  52. 	res += (1 - v[pos].p) * D(mask, pos + 1, k + 1);
  53.  
  54. 	return res - 2;
  55. }
  56.  
  57. int main()
  58. {
  59. 	int b;
  60. 	double f;
  61. 	cin >> b >> t >> f;
  62.  
  63. 	for (int i = 0; i < b; ++i)
  64. 	{
  65. 		S s;
  66. 		s.mask = 1 << i;
  67.  
  68. 		cin >> s.p >> s.s;
  69.  
  70. 		for (int j = 0; j < t; ++j)
  71. 		{
  72. 			v.push_back(s);
  73. 			s.p *= f;
  74. 		}
  75. 	}
  76.  
  77. 	sort(v.begin(), v.end());
  78.  
  79. 	double res = D(0, 0, 0);
  80.  
  81. 	printf("%0.9lf\n", res);
  82.  
  83. 	return 0;
  84. }
Success #stdin #stdout 0s 5436KB
comments (?)
stdin
copy 
2 2 0.500000
0.750000 100
0.750000 20
stdout
copy 
95.625000000
https://ideone.com/cilqEU
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 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!