0
Your rating: None

CodeChef submission 64961 (C++ 4.0.0-8)

CodeChef submission 64961 (C++ 4.0.0-8) plaintext list. Status: AC, problem F6, contest AUG09. By gmark (Mark Greve), 2009-08-05 17:39:46.
  1. // Divide and Conquer
  2. // Source: CodeChef August 2009 Algorithm Challenge
  3. // CodeChef ID: F6
  4. // Date: 03-08-2009
  5. // Author: Mark Greve
  6.  
  7. #include <algorithm>
  8. #include <bitset>
  9. #include <cassert>
  10. #include <cctype>
  11. #include <cmath>
  12. #include <cstdio>
  13. #include <cstdlib>
  14. #include <cstring>
  15. #include <ctime>
  16. #include <deque>
  17. #include <functional>
  18. #include <iomanip>
  19. #include <iostream>
  20. #include <list>
  21. #include <map>
  22. #include <numeric>
  23. #include <queue>
  24. #include <set>
  25. #include <sstream>
  26. #include <stack>
  27. #include <string>
  28. #include <utility>
  29. #include <vector>
  30. using namespace std;
  31.  
  32. #define MP make_pair
  33. typedef pair<double, double> pdd;
  34. const double EPS=1e-9;
  35.  
  36. void verify_sol(double k, const vector<pair<int, double> >& v) {
  37. 	vector<pair<double,int> > p;
  38. 	p.push_back(MP(1.0, 0));
  39. 	int cnt = 1;
  40. 	for (int i=0;i<v.size();++i) {
  41. 		for (int j=0;j<p.size();++j) if (v[i].first==p[j].first) {
  42. 			pair<double,int> x = p[j];
  43. 			p.erase(p.begin()+j);
  44. 			p.push_back(MP(v[i].second, cnt));
  45. 			p.push_back(MP(x.second - v[i].second, x.first));
  46. 			break;
  47. 		}
  48. 		sort(p.begin(),p.end());
  49. 		assert(v.back().second <= k*v[0].second + EPS);
  50. 	}
  51. }
  52.  
  53.  
  54. void solve(double k) {
  55. 	//cout << "K " << k << endl;
  56. 	int d;
  57. 	for (d=1;k >= pow(2.0,(d-1)/double(d));++d); 
  58. 	--d;
  59. 	d *= 2;
  60. 	//cout << "\tD " << d << endl;
  61. 	double r = pow(2.0,1./(d/2));
  62. 	//cout << "\tR " << r << endl;
  63. 	int vars = (d+1)/2;
  64. 	double x = (r-1)/(2*(pow(r,vars) - 1));
  65. 	//cout << "\tVARS " << vars << endl;
  66.  
  67. 	vector<pdd> l;
  68. 	double z = x;
  69. 	for (int i=0;i<2*vars;++i) {
  70. 		l.push_back(MP(z,z));
  71. 		//cout << "\tPUSH " << z << endl;
  72. 		if (i%2==1) z *= r;
  73. 	}
  74. 	
  75. 	vector<pdd> v;
  76. 	while (l.size()>1) {
  77. 		pdd a = l[0];
  78. 		pdd b = l[1];
  79. 		l.erase(l.begin(),l.begin()+2);
  80. 		//cout << "\tPPP " << a.second << " other " << b.second << " sum " << a.second + b.second << endl;
  81. 		v.push_back(MP(a.second, a.second + b.second));
  82. 		l.push_back(MP(a.second, a.second + b.second));
  83. 	}
  84.  
  85. 	printf("%d\n", d);
  86. 	vector<int> idx;
  87. 	idx.push_back(0);
  88. 	reverse(v.begin(),v.end());
  89. 	int cnt = 0;
  90. 	vector<pair<int, double> > sol;
  91. 	for (int i=0;i<v.size();++i) {
  92. 		int id = idx[cnt];
  93. 		++cnt;
  94. 		sol.push_back(MP(id,v[i].first));
  95. 		printf("%d %.10lf\n", id, v[i].first);
  96. 		idx.push_back(id);
  97. 		idx.push_back(cnt);
  98. 	}
  99. 	//verify_sol(k, sol);
  100. }
  101.  
  102. int main() { for (double k; cin >> k; solve(k)); }
  103.

Comments