赛时以为题意是个纳什均衡，写完之后第三个样例卡了很久。这种博弈论能不能把策略模型写清楚啊。/fn

题意：

有 道题，第 道题分数为 ，你和 Tourist 一起做这些题，规则如下：

• 每一回合，你和 Tourist 分别选出一道题，选择时你们互不了解对方的选项；
• 如果你选的题和 Tourist 一样，那么就删除这道题，如果 道题已经删光那么游戏结束并且你获得零分，否则进入下一回合；
• 如果你选的题和 Tourist 不一样，那么游戏结束，你的得分是你这回合选的这道题的得分。

Tourist 想要最小化你的得分，请问 Tourist 在最优策略下，你期望最多能获得多少分，以浮点数形式输出。

ix35 的注解：Tourist 的决策是基于概率的，也就是可以以一定权重随机选择某道题，而他的目标是使得你在这种情况下任意选择一道题，最大的期望得分最小。

首先肯定状压，设 表示当前局面为集合 的最大期望收益。

设 ， 中第 道题分数为 ，去除第 题后，你在剩下的题中期望收益为 ，Tourist 的策略是以 概率选择第 道题，那么 就是 考虑二分答案，设当前二分的值为 ，写出答案 的条件，即存在一组 满足： 令 ，当 时，，当 时，。 先不管。

上述式子启示我们将 与 对 的限制分开讨论。

对于 的，可以直接由条件 得到 ，此时 ，对于 的，直接取 ，显然此时的 都取到下界，这意味着只有此时 ，条件才可能满足。另一方面，因为肯定有一个 （考虑 最大的即可），所以对于 小于 的，剩下的那部分可以直接加到 的 上。

所以条件可以改写为： 如果真进行二分可以做到 。过不去。

因为满足这个条件说明答案 ，所以最小的满足该条件的 就是答案的最大值，这类似强对偶定理。条件 非常简单，给定了一个 的下界，而条件 中的 其实是个关于 的分段一次函数，且每段斜率都为负。所以我们可以对每段求出函数值等于 的位置，这也给 提供了一个下界。

这些下界都可以 计算得到。故总时间复杂度为 。可以通过。

#include <bits/stdc++.h>
using namespace std;
#define ppc __builtin_popcount
const int N = 25,Sz = 1 << 22;
typedef double db;
int n,a[N];
db f[Sz],b[N];
inline db Solve(int S) {
	db lim = 0;
	vector<int> id2;id2.reserve(n);
	for(int i = 0;i < n;i++) if((S >> i) & 1) {
		if(b[i] >= a[i]) lim = max<db>(lim,a[i]);
		else id2.push_back(i);
	}
	db sk = 0,sb = 0;
	for(int t = (int)id2.size() - 1;t >= 0;t--) {
		db L = !t ? 0 : a[id2[t - 1]],R = a[id2[t]];
		sk += 1.0 / (b[id2[t]] - a[id2[t]]);
		sb += (-a[id2[t]]) / (b[id2[t]] - a[id2[t]]);
		
		db x = (1 - sb) / sk;
		x = min(x,R);
		if(x >= L) lim = max(lim,x);
	}
	return lim;
}
int main() {
	cin >> n;
	for(int i = 0;i < n;i++) cin >> a[i];
	sort(a,a + n);
	for(int S = 0;S < (1 << n);++S) {
		if(ppc(S) <= 1) continue;
		for(int i = 0;i < n;i++)
			if((S >> i) & 1) 
				b[i] = f[S - (1 << i)];
		f[S] = Solve(S);
	}
	printf("%.12lf\n",f[(1 << n) - 1]);
	return 0;
}