Mobile Computing

[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem E

[解説]

総当り。
詳細は後日書きたいと思います。

[サンプルプログラム]

001 #include<stdio.h>
002 #include<iostream>
003 #include<vector>
004 #include<algorithm>
005 using namespace std;
006 #define MAX 6
007 #define NON -1
008 #define ROOT 0
009 #define TO_LEAF 0
010 #define TO_NODE 1
011 
012 struct Node{
013     int left, right;
014     double weight;
015 };
016 
017 class Tree{
018     public:
019     Node nodes[MAX*2];
020     int size;
021     vector<int> leaves, internals;
022     
023     Tree(){
024         for ( int i = 0; i < MAX*2; i++ ){
025             nodes[i].left = nodes[i].right = NON;
026             nodes[i].weight = 0.0;
027         }
028     }
029     
030     double getWidth(){
031         double maxx, minx;
032         maxx = minx = 0.0;
033         parse(0, 0.0, maxx, minx);
034         return maxx - minx;
035     }
036     
037     void parse(int u, double x, double &maxx, double &minx){
038         maxx = max( maxx, x );
039         minx = min( minx, x );
040         double n, m;
041         int left = nodes[u].left;
042         int right = nodes[u].right;
043         if ( left == NON ) return;
044         n = nodes[left].weight;
045         m = nodes[right].weight;
046         parse(left, x - m/(n+m), maxx, minx);
047         parse(right, x + n/(n+m), maxx, minx);
048     }
049     
050     double getWeight(int u){
051         if ( nodes[u].left == NON ) return nodes[u].weight;
052         nodes[u].weight = getWeight(nodes[u].left) + getWeight(nodes[u].right);
053         return nodes[u].weight;
054     }
055 };
056 
057 double R;
058 int stones[MAX];
059 int nstone;
060 
061 double maxv;
062 
063 void check(Tree u){
064     sort( stones, stones + nstone );
065     do {
066         for ( int i = 0; i < nstone; i++ ){
067             u.nodes[u.leaves[i]].weight = stones[i];
068         }
069         u.getWeight(ROOT);
070         double width = u.getWidth();
071         if ( width < R ) maxv = max( maxv, width );
072     } while ( next_permutation( stones, stones + nstone )) ;
073 }
074 
075 void makeTree(Tree u){
076     if ( u.leaves.size() == nstone && u.internals.size() == 0 ) check(u);
077     if ( u.leaves.size() + u.internals.size()*2 > nstone ) return;
078     
079     Tree v;
080     
081     for ( int i = 0; i < u.internals.size(); i++ ){
082         int parent = u.internals[i];
083         for ( int a = 0; a < 2; a++ ){
084             for ( int b = 0; b < 2; b++ ){
085                 v = u;
086                 v.nodes[parent].left = v.size++;
087                 v.nodes[parent].right = v.size++;
088                 if ( a == TO_LEAF ) v.leaves.push_back(v.size-2);
089                 else v.internals.push_back(v.size-2);
090                 if ( b == TO_LEAF ) v.leaves.push_back(v.size-1);
091                 else v.internals.push_back(v.size-1);
092                 v.internals.erase( v.internals.begin() + i );
093                 makeTree(v);
094             }
095         }
096     }
097 }
098 
099 void compute(){
100     if ( nstone == 1 ) {
101         printf("%.9lf\n", 0.0); return;
102     }
103     Tree root = Tree();
104     root.internals.push_back(ROOT);
105     root.size = 1;
106     maxv = -1;
107     makeTree(root);
108     if ( maxv < 0.0 ) cout << "-1" << endl;
109     else printf("%.9lf\n", maxv);
110 }
111 
112 void input(){
113     cin >> R >> nstone;
114     for ( int i = 0; i < nstone; i++ ) cin >> stones[i];
115 }
116 
117 main(){
118     int tcase; cin >> tcase;
119     for ( int i = 0; i < tcase; i++ ){
120         input();
121         compute();
122     }
123 }