Uva 1354 Mobile Computing

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <ctime>
  6 #include <set>
  7 #include <map>
  8 #include <list>
  9 #include <stack>
 10 #include <queue>
 11 #include <string>
 12 #include <vector>
 13 #include <fstream>
 14 #include <iterator>
 15 #include <iostream>
 16 #include <algorithm>
 17 using namespace std;
 18 #define LL long long
 19 #define INF 0x3f3f3f3f
 20 #define MOD 1000000007
 21 #define eps 1e-5
 22 #define MAXN 110
 23 #define MAXM 100
 24 #define dd {cout<<"debug"<<endl;}
 25 #define pa {system("pause");}
 26 #define p(x) {cout<<x<<endl;}
 27 #define pd(x) {printf("%.7lf\n", x);}
 28 #define k(x) {printf("Case %d: ", ++x);}
 29 #define s(x) {scanf("%d", &x);}
 30 #define sd(x) {scanf("%lf", &x);}
 31 #define mes(x, d) {memset(x, d, sizeof(x));}
 32 #define do(i, x) for(i = 0; i < x; i ++)
 33 #define dod(i, x, l) for(i = x; i >= l; i --)
 34 #define doe(i, x) for(i = 1; i <= x; i ++)
 35 int n;
 36 double r, ans;
 37 double w[MAXN], v[MAXN];
 38 double ll[MAXN], rr[MAXN];
 39 bool vis[MAXN];
 40 int order[MAXN];
 41 void read()
 42 {
 43     scanf("%lf", &r);
 44     scanf("%d", &n);
 45     for (int i = 1; i <= n; i ++)
 46         scanf("%lf", &w[i]);
 47 }
 48 void get_ans(int u)
 49 {
 50     memset(ll, 0, sizeof(ll));
 51     memset(rr, 0, sizeof(rr));
 52     memset(v, 0, sizeof(v));
 53 
 54     for (int i = u; i > 0; i --)
 55     {
 56         if (order[i] == -1)
 57         {
 58             int x = i * 2;
 59             int y = i * 2 + 1;
 60             v[i] = v[x] + v[y];
 61             double li = v[y] / v[i];
 62             double ri = v[x] / v[i];
 63 
 64             ll[i] = min(-li + ll[x], ri + ll[y]);
 65             rr[i] = max(-li + rr[x], ri + rr[y]);
 66         }
 67         else if (order[i])
 68         {
 69             v[i] = w[order[i]];
 70         }
 71     }
 72 
 73     double temp = rr[1] - ll[1];
 74     //printf("%.9lf\n", temp);
 75     if (temp - r < eps && temp > ans)
 76         ans = temp;
 77 }
 78 
 79 void dfs(int u, int num, int count)
 80 {
 81     //printf("%d %d %d\n", u, num, count);
 82     if (count == 0)
 83     {
 84         get_ans(u - 1);
 85         return ;
 86     }
 87     else if (order[u / 2] != -1)
 88     {
 89         dfs(u + 1, num, count);
 90     }
 91     else
 92     {
 93         if (count > num)
 94         {
 95             order[u] = -1;
 96             dfs(u + 1, num + 1, count);
 97             order[u] = 0;
 98         }
 99 
100         if (num == 1 && count > 1)
101             return ;
102         for (int i = 1; i <= n; i ++)
103             if (!vis[i])
104             {
105                 vis[i] = true;
106                 order[u] = i;
107                 dfs(u + 1, num - 1, count - 1);
108                 order[u] = 0;
109                 vis[i] = false;
110             }
111     }
112 }
113 void solve()
114 {
115     memset(vis, false, sizeof(vis));
116     memset(order, 0, sizeof(order));
117     ans = -1;
118     if (n == 1) printf("%.10lf\n", 0.0);
119     else
120     {
121         order[1] = -1;
122         dfs(2, 2, n);
123         printf(ans == -1? "-1\n" : "%.10lf\n", ans);
124     }
125 }
126 
127 int main()
128 {
129     int T;
130     scanf("%d", &T);
131     while (T --)
132     {
133         read();
134         solve();
135     }
136     return 0;
137 }