1261-Mobile Computing

問題概要

ある場所にはたくさんの美しい石がある．そして，そこに住んでいる人々は石を集めることが好きであった．．
そして人々は集めた石を持って帰り美しいModileアートを作るのであった．

さてここではModileは以下のように再帰的に定義される．
・紐によって吊されている石
・長さが1の棒で，両端にさらに"Mobile"が吊されている．そして，この棒は重心に紐で吊されている．

部屋の幅を越えず，かつ全ての石を使ったMobileのうち，もっとも幅が広いものを求めよ

解法

全探索して，全ての作れるMobileを求める．

実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <fstream>
using namespace std;

typedef long long int lli;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)

#define dout(...) printf(__VA_ARGS__);fflush(stdout);
int s;
int stone[6];
double width;
int T;

struct Rod{
	Rod *left,*right;
	int lw,rw,w;
	int used;
	Rod(int ww=0,int us=0){
		left=right=0;lw=rw=w=0;
		w=ww;used=us;
	}
};
vector<Rod> rods[7];//i個用いて作れるモビール
double lx,rx;
void dfs(const Rod &r,double x){
	//cout<<x<<endl;
	lx=min(lx,x);rx=max(rx,x);
	if(!r.left)return;//何もない
	double n=r.lw,m=r.rw;
	//cout<<n<<","<<m<<endl;
	double a=m/(n+m);
	double b=1-a;
	dfs(*r.right,x+b);
	dfs(*r.left,x-a);
}
void solve(){
	REP(i,s){
		rods[1].push_back(Rod(stone[i],1<<i));
	}
	for(int i=1;i<=s;i++){
		for(int j=1;j<=i;j++){
			if(i+j>s)continue;
			for(int x=0;x<(int)rods[i].size();x++){
				for(int y=0;y<(int)rods[j].size();y++){
					if(j==i&&x<=y)continue;
					if(rods[i][x].used&rods[j][y].used)continue;
					Rod next;
					next.left=&rods[i][x];
					next.right=&rods[j][y];
					next.lw=rods[i][x].w;
					next.rw=rods[j][y].w;
					next.w=next.lw+next.rw;
					next.used=rods[i][x].used|rods[j][y].used;
					rods[i+j].push_back(next);
					swap(next.left,next.right);
					swap(next.lw,next.rw);
					rods[i+j].push_back(next);
				}
			}
		}
	}
	double ans=-1;
	REP(i,rods[s].size()){
		lx=rx=0;
		dfs(rods[s][i],0);
		if(rx-lx<=width){
			ans=max(ans,rx-lx);
		}
	}
	if(ans<0)cout<<"-1"<<endl;
	else cout<<setprecision(15)<<setiosflags(ios::fixed)<<ans<<endl;
}
int main(){
	cin>>T;
	while(T--){
		cin>>width;
		cin>>s;
		REP(i,s)cin>>stone[i];
		REP(i,7)rods[i].clear();
		solve();
	}
	return 0;
}