Advertisement
Guest User

Untitled

a guest
Nov 28th, 2014
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.79 KB | None | 0 0
  1. {2} -> {8, 2}
  2. {2} -> {2, 8}
  3.  
  4. {8, 2} -> {4, 8, 2}
  5. {2, 8} -> {2, 8, 4}
  6.  
  7. {4, 8, 2} -> {1, 4, 8, 2}
  8. {4, 8, 2} -> {4, 8, 2, 1}
  9. {2, 8, 4} -> {1, 2, 8, 4}
  10. {2, 8, 4} -> {2, 8, 4, 1}
  11.  
  12. {1, 4, 8, 2} -> {2, 4, 8, 2}
  13. {1, 4, 8, 2} -> {1, 4, 8, 4}
  14. {4, 8, 2, 1} -> {16, 2, 1}
  15.  
  16. {1, 4, 8, 4} -> {1, 4, 16}
  17. {16, 2, 1} -> {32, 2, 1}
  18.  
  19. {1, 4, 16} -> {1, 4, 16, 4}
  20. {32, 2, 1} -> {4, 32, 2, 1}
  21.  
  22. {1, 4, 16, 4} -> {1, 4, 16, 8}
  23.  
  24. {1, 4, 16, 8} -> {1, 4, 16, 8, 4}
  25.  
  26. no
  27. {2} -> {16, 2}
  28. {2} -> {2, 16}
  29.  
  30. {2} -> {4, 2}
  31. {2} -> {2, 4}
  32. {16, 2} -> {4, 16, 2}
  33.  
  34. {2, 16} -> {2, 16, 8}
  35. {4, 2} -> {8, 4, 2}
  36. {2, 4} -> {2, 4, 8}
  37.  
  38. {4, 16, 2} -> {2, 4, 16, 2}
  39. {4, 16, 2} -> {4, 16, 4}
  40. {2, 16, 8} -> {2, 16, 8, 4}
  41. {8, 4, 2} -> {4, 8, 4, 2}
  42.  
  43. no
  44. {2} -> {4}
  45. {2} -> {2, 4}
  46.  
  47. {4, 2} -> {2, 4, 2}
  48. {4, 2} -> {8}
  49.  
  50. lll
  51. lll
  52.  
  53. #include <iostream>
  54. #include <algorithm>
  55. #include <cstdio>
  56. #include <cstdlib>
  57. #include <ctime>
  58. #include <memory.h>
  59. #include <cmath>
  60. #include <string>
  61. #include <cstring>
  62. #include <queue>
  63. #include <vector>
  64. #include <set>
  65. #include <deque>
  66. #include <map>
  67. #include <functional>
  68. #include <numeric>
  69. #include <sstream>
  70. #include <complex>
  71. #include <cassert>
  72.  
  73. typedef long double LD;
  74. typedef long long LL;
  75. typedef unsigned long long ULL;
  76. typedef unsigned int uint;
  77.  
  78. #define PI 3.1415926535897932384626433832795
  79. #define sqr(x) ((x)*(x))
  80.  
  81. using namespace std;
  82.  
  83. #include <map>
  84. map< vector<int>, int> reg;
  85. vector< vector<int> > vec(1);
  86. vector< pair<int, char> > pre(1);
  87.  
  88. int idn = 0;
  89. int regist(vector<int>& a) {
  90. int ph = 0;
  91. for (int i = 1; i < a.size(); ++i) {
  92. if (ph == 0) {
  93. if (a[i - 1] > a[i]) ph = 1;
  94. } else {
  95. if (a[i - 1] < a[i]) return -1;
  96. }
  97. }
  98.  
  99. int& id = reg[a];
  100. if (!id) id = ++idn;
  101. vec.push_back(a);
  102. pre.push_back(make_pair(0, 0));
  103. return id;
  104. }
  105.  
  106. void out(vector<int>&a) {
  107. cout << "{";
  108. for (int i = 0; i < a.size(); ++i) {
  109. if (i) cout << ", ";
  110. cout << a[i];
  111. }
  112. cout << "}";
  113. }
  114.  
  115. void output(vector<int>&a, vector<int>& b) {
  116. out(a);
  117. cout << " -> ";
  118. out(b);
  119. cout << endl;
  120. }
  121.  
  122.  
  123. int main() {
  124. freopen(".in", "r", stdin);
  125. freopen(".out", "w", stdout);
  126. ios::sync_with_stdio(false);
  127.  
  128. int T;
  129. cin >> T;
  130. while (T--) {
  131. int n;
  132. cin >> n;
  133.  
  134. vector<int> all;
  135. {
  136. int x;
  137. cin >> x;
  138. vector<int> v(1, x);
  139. int id = regist(v);
  140. all.push_back(id);
  141. pre[id] = make_pair(0, 'l');
  142. }
  143. for (int i = 1; i < n; ++i) {
  144. int x;
  145. cin >> x;
  146. vector<int> q;
  147. for (int j = 0; j < all.size(); ++j) {
  148. {
  149. vector<int> v = vec[ all[j] ];
  150. while (v.size() && v.front() == x) {
  151. x += x;
  152. v.erase(v.begin());
  153. }
  154. v.insert(v.begin(), x);
  155. int id = regist(v);
  156. if (id != -1) {
  157. pre[id] = make_pair(all[j], 'l');
  158. q.push_back(id);
  159. output(vec[ all[j] ], v);
  160. }
  161. }
  162. {
  163. vector<int> v = vec[ all[j] ];
  164. while (v.size() && v.back() == x) {
  165. x += x;
  166. v.pop_back();
  167. }
  168. v.push_back(x);
  169. int id = regist(v);
  170. if (id != -1) {
  171. pre[id] = make_pair(all[j], 'l');
  172. q.push_back(id);
  173. output(vec[ all[j] ], v);
  174. }
  175. }
  176. }
  177. cout << endl
  178. ;
  179. sort(q.begin(), q.end());
  180. q.erase(unique(q.begin(), q.end()), q.end());
  181. all.swap(q);
  182. }
  183. bool found = 0;
  184. for (int i = 0; i < all.size(); ++i)
  185. if (vec[all[i]].size() == 1) {
  186. int x = all[i];
  187. string s;
  188. while (x != 0) {
  189. s += pre[x].second;
  190. x = pre[x].first;
  191. }
  192. reverse(s.begin(), s.end());
  193. cout << s << "\n";
  194. found = 1;
  195. }
  196. if (!found) {
  197. cout << "no\n";
  198. }
  199. }
  200.  
  201. return 0;
  202. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement