CF1267G Game Relics

, ,

Game Relics

Solution

真的好退役了/kk

抽的期望价值是递增的。所以一个简单的策略是先抽后买。那么这些操作肯定有一个分界点。

令已经有了 $i$ 个物品，已有的物品买的价值和 $j$，考虑选下一个。抽的权值为 $\dfrac{x}{2}(\dfrac{n}{n-i}+1)$，买的平均价值为 $\dfrac{sum-j}{n-i}$。如果买的平均价值小于抽的期望价值，则开始买。观察到两者只与 $i$ 和权值和 $j$ 有关。令 $f_{i,j}$ 为到这个状态的概率。转化为求方案数，做背包，总方案数为 $\dbinom{n}{i}$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 105
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,a[maxn],sum;
double c[maxn][maxn], f[maxn][maxn*maxn],ans;
signed main(void){
//	freopen("1.in","r",stdin);
	int i,j,k;
	read(n);read(m);
	c[0][0]=1;
	for (i=1;i<=n;i++) {
		c[i][0]=1;
		for (j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];
	}
	f[0][0]=1;
	for (i=1;i<=n;i++) {
		read(a[i]);sum+=a[i];
		for (k=i;k>=1;k--)
			for (j=a[i];j<=sum;j++)
				f[k][j]+=f[k-1][j-a[i]];
	}        
	for (i=0;i<n;i++)
		for (j=0;j<=sum;j++) {
			ans+=min(1.0*(sum-j)/(n-i),1.0*m/2*(1.0*n/(n-i)+1))*f[i][j]/c[n][i];
		}
	printf("%.10lf",ans);                                                                             
	return 0;
}