Mobile Computing
2007.08.24 22:26 ACM/ICPC 2005
[問題] 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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |