一句话题解系列(一):NWERC 2017

一句话解答 NWERC 2017 比赛的所有问题

写在前面

前段时间通关了 WF2019,感觉有点上头了。这两天想刷刷各种区域赛的题,首先从欧洲的 ERC 系列开始吧。这次做的是 NWERC 2017 的赛题,包括正赛的 A-J 题一共 10 题。

NWERC 是西北欧的 ACM 区域赛决赛,参与者包括英国、法国、德国、比利时、芬兰等国的大学。这个赛区的题目往往码量不大,注重思维能力,题目的创新性很高。

由于对算法题来说,写代码往往很快,搞博客比较慢,想写出让别人能够看懂的题解就更难了。由于精力有限,这次就不再写详细的题解了,每题写一句话,概括一下我的思考过程。

相关资料:

比赛官网 https://people.bath.ac.uk/masjhd/NWERC/

试题与官方数据下载 https://people.bath.ac.uk/masjhd/NWERC/news/index.html

 

A. Ascending Photo

乍一看,所有相邻的数连在一起,别的数剪开就可以了,但交一发 WA 了。写了对拍才发现有反例如 1 2 3 1 2 3 (1 / 2 3 / 1 2 / 3),因此考虑修正这些情况:对 x x+1 x+2 且 x+1 出现至少两次的情况进行一下搜索,枚举拆前面还是拆后面。

#include <bits/stdc++.h>
#include <random>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
inline int read(){
	register int res=0, c;
	while(c=getchar(), c<'0'||c>'9');
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return res;
}
int solve(vector<int> s){
	int N=s.size()-1;
	int dup = 0, j = 1;
	for(int i=2; i<=N; i++){
		if(s[i]==s[i-1])dup++;
		else s[++j]=s[i];
	}
	s.resize(j+1);
	auto t=s;
	sort(t.begin()+1, t.end());
	t.erase(unique(t.begin()+1, t.end()), t.end());
	for(int i=1; i<=j; i++){
		s[i]=lower_bound(t.begin()+1, t.end(), s[i]) - t.begin();
	}
	vector<vector<int>> ind(N+1);
	vector<int> vis(N+1), uniq(N+1, false);
	for(int i=1; i<j; i++){
		if(s[i]+1==s[i+1])ind[s[i]].push_back(i);
	}
	for(auto i:s){
		uniq[i]++;
	}
	auto dfs = [&](auto Self, int x, int y)->bool{
		for(auto i:ind[x]){
			if(!vis[i] && (uniq[x+1]==1 || !vis[i+1])){
				vis[i]=vis[i+1]=true;
				return true;
			}
		}
		for(auto i:ind[x]){
			if(!vis[i] && i+1<j){
				//assert(vis[i+2]==false);
				vis[i+2]=false;
				if(Self(Self, x+1, y)){
					vis[i]=true;
					return true;
				}
				vis[i+2]=true;
			}
		}
		return false;
	};
	int ans=0;
	for(int i=t.size()-1; i; i--){
		if(dfs(dfs, i, 0)) ans++;
	}
	return j - 1 - ans;
}
int solve2(vector<int> s){
	int N=s.size()-1;
	for(int i=0; i<N; i++){
		vector<int> p(N, 0);
		for(int j=N-i; j<N; j++){
			p[j]=1;
		}
		do{
			vector<int> t;
			t.reserve(N);
			auto test=[&]()->bool{
				for(auto i=1; i<N; i++)if(t[i]<t[i-1])return false;
				return true;
			};
			auto cmp = [&](int a, int b)->bool{
				do{
					a++, b++;
					if(s[a]<s[b])return true;
					else if(s[a]>s[b])return false;
				} while(a<N && b<N && !p[a] && !p[b]);
				if(a==N || p[a])return true;
				return false;
			};
			set<int, decltype(cmp)> st(cmp);
			for(int i=1; i<N; i++){
				if(p[i]) st.insert(i);
			}
			st.insert(0);
			while(st.size()){
				int top = *st.begin();
				do t.push_back(s[++top]); while(top<N && !p[top]);
				st.erase(st.begin());
			}
			if(test())return i;
		} while(next_permutation(p.begin()+1, p.end()));
	}
}
int main(){
	/*vector<int> s={0,1,1,1,2,2,2,3,3,3,3,4};
	default_random_engine generator{random_device{}()};
	while(true){
		shuffle(s.begin()+1, s.end(), generator);
		int a=solve(s), b=solve2(s);
		if(a!=b){
			for(int i=1; i<s.size(); i++){
				printf("%d%c", s[i], i==s.size()-1?'\n':' ');
			}
			printf("%d %d\n", a, b);
			return 0;
		}
		else puts("ok.");
	}*/
	int N=read();
	vector<int> s(N+1);
	for(int i=1; i<=N; i++){
		s[i]=read();
	}
	printf("%d\n", solve(s));
}

 

B. Boss Battle

n<=3 时一枪即可搞定;n>3时每一枪都可以减少 boss 的一个可能的位置,因此答案为 max(n-2, 1)。

代码略。

 

C. Connect the Dots

几何题,简单的贪心、dp、爆搜的想法都行不通。考虑每个点与上一个点的连线的延长线,事实上构成了一个扇形;而一个扇形中任一点与下一个点的连接线的延长线依然是一个扇形(有时会退化成一条射线)。从 3 号点开始,每个点如果在上一个扇形内,则可以“一笔画”到这个点,否则答案+1。利用以上结论,维护并更新扇形即可得到答案。

AC 代码:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<double, double>;
inline int read(){
	register int res=0, c;
	while(c=getchar(), c<'0'||c>'9');
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return res;
}
const double pi=3.14159265359, eps=1e-9;
void normal(double& x){   // 把角度 x 化到 [0, 2pi) 区间内
	while(x>2*pi-eps)x-=2*pi;
	while(x<-eps)x+=2*pi;
	if(fabs(x)<=eps)x=0;
}
struct range{ // 表示一个扇形
	pii c;    // 扇形的圆心
	double a, b; // 扇形的角度
	bool can[2]; // 扇形的两边是闭区间还是开区间
	bool in(double d){ // d 角度在不在扇形内
		normal(a);
		normal(b);
		normal(d);
		if(fabs(b-a) < eps){
			return (fabs(d-b) < eps);
		}
		while(b<a)b+=2*pi;
		while(d<(can[0]?a-eps:a+eps))d+=2*pi;
		return d<(can[1]?b+eps:b-eps);
	}
	void swap(double d){ // 更新扇形,可能的角度为 a+pi, b+pi, d
		a-=pi;
		b-=pi;
		can[0]=can[1]=false;
		if(in(d)){
			return;
		}
		double test = d-a;
		normal(test);
		if(fabs(test-pi) < eps){
			b = d;
			can[1] = true;
		}
		else if(fabs(test) < eps){
			a = d;
			can[0] = true;
		}
		else if(test < pi){
			b = d;
			can[1] = true;
		}
		else{
			a = d;
			can[0] = true;
		}
	}
};
int main(){
	vector<pii> p(17);
	for(int i=4; i>=1; i--){
		for(int j=1; j<=4; j++){
			int x=read();
			p[x]={j, i};
		}
	}
	double d = atan2(p[2].second - p[1].second, p[2].first - p[1].first);
	range now = range{p[2], d, d, {true, true}};
	int ans = 1;
	for(int i=3; i<=16; i++){
		double d = atan2(p[i].second - now.c.second, p[i].first - now.c.first);
		if(now.in(d)){
			now = range{p[i], d, d, {true, true}};
		}
		else{
			now.c = p[i];
			now.swap(d);
			ans++;
		}
	}
	printf("%d\n", ans);
	return 0;
}

 

D. Dunglish

对正确的翻译和错误的翻译分别维护一个map<string, vector<string>>,则最终结果正确的数量 ,总数 ,相减得到错误的数量。

AC 代码:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using tii=tuple<int, int, int>;
inline int read(){
	register int res=0, c;
	while(c=getchar(), c<'0'||c>'9');
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return res;
}
int main(){
	vector<string> S;
	int N=read();
	for(int i=0; i<N; i++){
		string str;
		cin>> str;
		S.push_back(str);
	}
	int M=read();
	map<string, vector<string>> C, IC;
	for(int i=0; i<M; i++){
		string a, b, c;
		cin>> a>> b>> c;
		if(c[0]=='i'){
			IC[a].push_back(b);
		}
		else{
			C[a].push_back(b);
		}
	}
	string ans;
	long long ac=1, ai=1;
	bool flag=true;
	for(int i=0; i<N; i++){
		if(C[S[i]].size() + IC[S[i]].size()!=1){
			flag = false;
		}
		else ans += (C[S[i]].size()?C[S[i]][0]:IC[S[i]][0])+' ';
		ac *= C[S[i]].size();
		ai *= (C[S[i]].size() + IC[S[i]].size());
	}
	if(flag){
		cout<<ans<<endl<<(ac?"correct":"incorrect");
	}
	else{
		cout<<ac<<" correct\n"<<ai-ac<<" incorrect";
	}
	return 0;
}

 

E. English restaurant

组合+区间dp。首先添加 n 个容量无限大的桌子并排序,然后求前 i 个桌子前 j 天容纳的总人数和总方案数。为了计算这个,需要预处理 num 和 den 表示 [l, r] 的桌子装满人时的总人数和总方案数。最后 dp 的过程中需要前缀和优化。

还没想清楚细节,待补。先上标程代码:

#include <bits/stdc++.h>
using namespace std;
using ld = long double;
int n2(int n) { return n * (n + 1) / 2; }
void fadd(ld &a, ld &b, ld p, ld q) {
	a = a*q+b*p;
	b = b*q;
}
pair<int, int> rfrac(int l, int r, const vector<int> &c, int g) {
	int lb = min(g, l > 0 ? c[l - 1] : 0);
	int rb = min(g, c[r]);
	return {c[r] <= 211 ? n2(rb) - n2(lb) : 0, rb - lb};
}
int main() {
	int n, g, t;
	cin >> n >> g >> t;
	vector<int> c(n);
	for (int &v : c) cin >> v;
	sort(c.begin(), c.end());
	for (int i = 0; i < t; ++i) c.push_back(300), ++n;
	ld nCk[212][212];
	for (int i = 0; i <= 211; ++i) nCk[0][i] = 0, nCk[i][0] = 1;
	for (int i = 1; i <= 211; ++i)
		for (int j = 1; j <= 211; ++j)
			nCk[i][j] = nCk[i-1][j-1] + nCk[i-1][j];
	// num[i][j] / den[i][j] = E(guests | group sizes in (c[i-1], c[j]] ).
	ld num[211][211], den[211][211];
	for (int r = 0; r < n; ++r) {
		tie(num[r][r], den[r][r]) = rfrac(r, r, c, g);
		for (int l = r - 1; l >= 0; --l) {
			num[l][r] = 0;
			den[l][r] = 0;
			for (int k = l; k <= r; ++k) {
				ld sum = 0.0;
				ld ways = nCk[r-l][k-l];
				// Place k.
				ld a, b;
				tie(a, b) = rfrac(l, k, c, g);
				fadd(sum, ways, a, b);
				// Place <k.
				if (l < k) fadd(sum, ways, num[l][k-1], den[l][k-1]);
				// Place >k.
				if (k < r) fadd(sum, ways, num[k+1][r], den[k+1][r]);
				num[l][r] += sum;
				den[l][r] += ways;
			}
		}
	}
	// dp[groups [i..t)][tables [j..n)] with table j used
	ld dpn[211][211], dpd[211][211];
	for (int i = 0; i < 211; ++i)
		for (int j = 0; j < 211; ++j)
			dpn[i][j] = dpd[i][j] = 0;
	// Begin by computing suffixes including people that are sent away.
	for (int i = t - 1; i >= 0; --i) {
		for (int j = n - 1; j >= 0; --j) {
			// We have t-i groups and n-j tables.
			if (t-i <= n-j) {
				dpn[i][j] = num[j][j+t-i-1];
				dpd[i][j] = den[j][j+t-i-1];
			}
		}
	}
	// Add more segments.
	for (int i = t - 1; i >= 0; --i) {
		for (int j = n - 1; j >= 0; --j) {
			for (int ni = i + 1; ni < t; ++ni) {
				for (int ns = j + (ni-i) + 1; ns < n; ++ns) {
					ld sum = 0.0, ways = nCk[t-i][t-ni];
					fadd(sum, ways, num[j][j+(ni-i)-1], den[j][j+(ni-i)-1]);
					fadd(sum, ways, dpn[ni][ns], dpd[ni][ns]);
					dpn[i][j] += sum;
					dpd[i][j] += ways;
				}
			}
		}
	}
	// Loop over the smallest table to be seated, and the last group to be
	// seated.
	ld ansn = 0.0, ansd = 0.0;
	for (int l = 0; l < n; ++l)
		ansn += dpn[0][l], ansd += dpd[0][l];
	cerr << ansn << " / " << ansd << endl;
	printf("%.10lf\n", double(ansn / ansd));
	return 0;
}

 

F. Factor-Free Tree

挺有意思的题。乍一看能看到不少局部性质,但难以用来建树,因此观察整体性质。树的根节点一定与所有数互质,然后分成了左右两个子树,递归即可。为了 O(n) 查找一个区间中与所有数互质的数,预处理一下每个数往左边和往右边可以到哪里,这又要用到用扩展欧氏筛对 以内的数进行均摊 O(1) 因数分解,这都是常见套路,不再详述。

AC 代码:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using tii=tuple<int, int, int>;
inline int read(){
	register int res=0, c;
	while(c=getchar(), c<'0'||c>'9');
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return res;
}
int main(){
	int n=1e7;
	vector<short> pre(n+1, 0);
	vector<int> prime;
	for(int i=2; i<=n; i++){
		if(!pre[i]&&i<1e4) prime.push_back(i);
		for(auto j:prime){
			if(i*j>n)break;
			pre[i*j]=j;
			if(i%j==0)break;
		}
	}
	int N=read();
	vector<int> s(N+1);
	for(int i=1; i<=N; i++){
		s[i]=read();
	}
	map<int, int> lst;
	vector<int> L(N+1, 1), R(N+1, N);
	for(int i=1; i<=N; i++){
		for(int j=s[i]; j>1;){
			int t = pre[j]?pre[j]:j;
			if(lst[t]){
				L[i]=max(L[i], lst[t]+1);
				R[lst[t]]=min(R[lst[t]], i-1);
			}
			lst[t]=i;
			if(!pre[j])break;
			do j/=pre[j]; while(pre[j]==t);
			if(j==t)break;
		}
	}
	vector<int> ans(N+1);
	auto dfs = [&](auto Self, int l, int r, int fa)->void{
		if(l==r)ans[l]=fa;
		else if(l+1==r){
			if(R[l]!=l)ans[l]=fa, ans[r]=l;
			else goto bad;
		}
		else if(l+2==r){
			if(L[l+1]<=l && R[l+1]>=r)ans[l]=l+1, ans[r]=l+1, ans[l+1]=fa;
			else goto bad;
		}
		else{
			for(int i=0; i<=r-l; i++){
				int now = i&1?l+(i>>1):r-(i>>1);
 				if(L[now]<=l && R[now]>=r){
					ans[now]=fa;
					if(now>l)Self(Self, l, now-1, now);
					if(now<r)Self(Self, now+1, r, now);
					return;
				}
			}
			bad: exit(puts("impossible")&0);
		}
	};
	dfs(dfs, 1, N, 0);
	for(int i=1; i<=N; i++)printf("%d ", ans[i]);
	return 0;
}

 

G. Glyph Recognition

几何题,二分多边形边长,跨立实验判断线段交。写计算几何的两个心得:1. eps慎用,只在判等和取整的时候用;2. 边界、端点的情况尽量写特判。

AC 代码:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using tii=tuple<int, int, int>;
inline int read(){
	register int res=0, c;
	while(c=getchar(), c<'0'||c>'9');
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return res;
}
int main(){
	int n=1e7;
	vector<short> pre(n+1, 0);
	vector<int> prime;
	for(int i=2; i<=n; i++){
		if(!pre[i]&&i<1e4) prime.push_back(i);
		for(auto j:prime){
			if(i*j>n)break;
			pre[i*j]=j;
			if(i%j==0)break;
		}
	}
	int N=read();
	vector<int> s(N+1);
	for(int i=1; i<=N; i++){
		s[i]=read();
	}
	map<int, int> lst;
	vector<int> L(N+1, 1), R(N+1, N);
	for(int i=1; i<=N; i++){
		for(int j=s[i]; j>1;){
			int t = pre[j]?pre[j]:j;
			if(lst[t]){
				L[i]=max(L[i], lst[t]+1);
				R[lst[t]]=min(R[lst[t]], i-1);
			}
			lst[t]=i;
			if(!pre[j])break;
			do j/=pre[j]; while(pre[j]==t);
			if(j==t)break;
		}
	}
	vector<int> ans(N+1);
	auto dfs = [&](auto Self, int l, int r, int fa)->void{
		if(l==r)ans[l]=fa;
		else if(l+1==r){
			if(R[l]!=l)ans[l]=fa, ans[r]=l;
			else goto bad;
		}
		else if(l+2==r){
			if(L[l+1]<=l && R[l+1]>=r)ans[l]=l+1, ans[r]=l+1, ans[l+1]=fa;
			else goto bad;
		}
		else{
			for(int i=0; i<=r-l; i++){
				int now = i&1?l+(i>>1):r-(i>>1);
 				if(L[now]<=l && R[now]>=r){
					ans[now]=fa;
					if(now>l)Self(Self, l, now-1, now);
					if(now<r)Self(Self, now+1, r, now);
					return;
				}
			}
			bad: exit(puts("impossible")&0);
		}
	};
	dfs(dfs, 1, N, 0);
	for(int i=1; i<=N; i++)printf("%d ", ans[i]);
	return 0;
}

 

H. High Score

(初中)数学题。d 比较大的时候,全都加给一个人是最优的;d 比较小时暴力枚举即可。

AC 代码:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using tii=tuple<int, int, int>;
inline int read(){
	register int res=0, c, d=0;
	while(c=getchar(), c<'0'||c>'9')d=c=='-';
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return d?-res:res;
}
int main(int argc, char* argv[]){
	auto calc = [](int a, int b, int c){
		return 1ll*a*a + 1ll*b*b + 1ll*c*c + 7ll*min(a, min(b, c));
	};
	auto solve2 = [&](int a, int b, int c, int d){
		long long ans = -1e10;
		for(int turns = 0; turns < 3; turns++){
			swap(a, b);
			swap(b, c);
			for(int i=0; i<=min(d, 777); i++){
				for(int j=0; j<=min(d-i, 777); j++){
					ans = max(ans, calc(a+i, b+j, c+d-i-j));
				}
			}
		}
		return ans;
	};
	int T=read();
	while(T--){
		int a=read(), b=read(), c=read(), d=read();
		long long ans = solve2(a, b, c, d);
		printf("%lld\n", ans);
	}
	return 0;
}

 

I. Installing Apps

想象每次安装软件都是先使用 a[i] 的空间再释放 b[i]-a[i] 的空间,则容易想到安装软件的顺序是按照 b[i]-a[i] 从大到小排列。接下来就是比较简单的 dp 了,有 O(NK) 和 O(N^2) 两种写法。

O(NK) 代码:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using tii=tuple<int, int, int>;
inline int read(){
	register int res=0, c, d=0;
	while(c=getchar(), c<'0'||c>'9')d=c=='-';
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return d?-res:res;
}
int main(){
	int N=read(), K=read();
	vector<int> a(N+1), b(N+1), c(N+1);
	for(int i=1; i<=N; i++){
		a[i]=read();
		b[i]=read();
		c[i]=i;
	}
	sort(c.begin()+1, c.end(), [&](int i, int j){
		return a[i]-b[i] > a[j]-b[j];
	});
	vector<int> dp(K+1);
	vector<map<int, pii>> from(N+1);
	for(int i=1; i<=N; i++){
		for(int j=K-b[c[i]]; j>=0; j--){
			if(j+a[c[i]]<=K && dp[j+b[c[i]]]<dp[j]+1){
				dp[j+b[c[i]]]=dp[j]+1;
				from[i][j+b[c[i]]]={j, c[i]};
			}
		}
	}
	int ans=0; vector<int> ans2;
	pii p={0, 0};
	for(int i=1; i<=K; i++){
		if(ans<dp[i]){
			ans=dp[i];
			p={i, N};
		}
	}
	printf("%d\n", ans);
	while(p.second){
		if(from[p.second].count(p.first)){
			auto f = from[p.second][p.first];
			p.first = f.first;
			ans2.push_back(f.second);
		}
		p.second--;
	}
	for(int i=ans2.size()-1; ~i; i--)printf("%d ", ans2[i]);
	return 0;
}

O(N^2) 代码:

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using tii=tuple<int, int, int>;
inline int read(){
	register int res=0, c, d=0;
	while(c=getchar(), c<'0'||c>'9')d=c=='-';
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return d?-res:res;
}
int main(){
	int N=read(), K=read();
	vector<int> a(N+1), b(N+1), c(N+1);
	for(int i=1; i<=N; i++){
		a[i]=read();
		b[i]=read();
		c[i]=i;
	}
	sort(c.begin()+1, c.end(), [&](int i, int j){
		return a[i]-b[i] > a[j]-b[j];
	});
	vector<int> dp(N+1, K+1);
	vector<map<int, int>> from(N+1);
	dp[0]=0;
	for(int i=1; i<=N; i++){
		for(int j=i-1; j>=0; j--){
			if(dp[j+1] > dp[j]+b[c[i]] && dp[j]+a[c[i]] <= K){
				dp[j+1] = dp[j]+b[c[i]];
				from[i][j+1] = i;
			}
		}
	}
	vector<int> ans;
	for(int i=N; i; i--){
		if(dp[i]<=K){
			int j=N;
			while(i){
				if(from[j].count(i)){
					ans.push_back(c[j]);
					i--;
				}
				j--;
			}
			break;
		}
	}
	printf("%d\n", ans.size());
	for(int i=ans.size()-1; ~i; i--){
		printf("%d ", ans[i]);
	}
	return 0;
}

J. Juggling Troupe

思维(找规律)题,挺难想到的。首先看出一个不知道怎么证的结论:每次所有 2 一起扔球,和每个 2 分别扔球,最后的结果是一样的。因此可以把每个 2 的人分别考虑。这时别的人是 1 还是 2 对他来说都是一样的(因为接到球后下一秒都会扔),而 0 接到球之后就会“反弹”。因此对于每个 2 ,预处理出他的左边和右边的第一个 0 的位置,就可以知道他最后会在哪里变成一个 0。

代码略。

K. Knockout Tournament

动态规划。首先贪心地让胜率最低的人先和我们打,让胜率最高的人先互相血拼,用胜率为 0 的人补满 2^K 个位置。然后 dp[i][a] 表示第 i 轮 a 玩家获胜的概率, O(N^2) 转移一下即可。

AC 代码:

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using tii=tuple<int, int, int>;
inline int read(){
	register int res=0, c, d=0;
	while(c=getchar(), c<'0'||c>'9')d=c=='-';
	do{
		res=(res*10)+(c^48);
	} while(c=getchar(), c>='0'&&c<='9');
	return d?-res:res;
}
int main(int argc, char* argv[]){
	int N=read();
	int K=1;
	while((1<<K)<N)K++;
	vector<int> s(N+1);
	for(int i=1; i<=N; i++){
		s[i]=read();
	}
	sort(s.begin()+2, s.end());
	vector<int> t;
	t.reserve(1<<K);
	int cnt = (1<<K)-N;
	for(int i=1; i<=N; i++){
		t.push_back(s[i]);
		if(cnt-->0)t.push_back(0);
	}
	N = 1<<K;
	vector<vector<double>> f(K+1, vector<double>(N, 0));
	f[0].swap(*new vector<double>(N, 1));
	for(int i=1; i<=K; i++){
		for(int a=0; a<N; a++)if(t[a]){
			int lower = (a^(1<<i-1))&((1<<K)-(1<<i-1));
			int upper = (a^(1<<i-1))|((1<<i-1)-1);
			//printf("Debug: a=%d i=%d lower=%d upper=%d\n", a, i, lower, upper);
			for(int j=lower; j<=upper; j++){
				f[i][a] += f[i-1][j] * t[a] / (t[a]+t[j]);
			}
			f[i][a] *= f[i-1][a];
		}
	}
	printf("%.9lf\n", f[K][0]);
	return 0;
}