#include #include #include #include #include using namespace std; int parse(const string& s) { istringstream iss(s); int length = 0; int last = -1; char c; while (iss >> c){ switch (c) { case 'R': int i; iss >> i; length += 64 /i; last = 64 / i; break; case '.': length += last / 2; last /= 2; break; default: cout << "ERROR" << endl; return -1; } } return length; } //1,2,4,8,16,32,64 static const string R[] = {"R1", "R2", "R4", "R8", "R16", "R32", "R64", }; static const string PERIOD = "."; bool compare(const string& a, const string& b) { return a.size() < b.size() || a.size() == b.size() && a < b; } void createSmallAnswers(int length, vector& smallAnswers) { vector > memo(max(length + 1, 64 + 1), vector(7)); memo[1][6] = "R64"; memo[2][5] = "R32"; memo[4][4] = "R16"; memo[8][3] = "R8"; memo[16][2] = "R4"; memo[32][1] = "R2"; memo[64][0] = "R1"; for (int i = 1; i < length; ++i){ for (int from = 0; from < 7; ++from){ if (memo[i][from].empty()){ continue; } for (int to = 0; to < 7; ++to){ const string candidate = memo[i][from] + ((from + 1 != to) ? R[to] : PERIOD); const int next = i + (1 << (6 - to)); if (next > length){ continue; } if (memo[next][to].empty() || compare(candidate, memo[next][to])) { memo[next][to] = candidate; } } } } smallAnswers.clear(); for (int l = 0; l <= length; ++l){ string minString; for (int i = 0; i < 7; ++i){ if (memo[l][i].empty()){ continue; } if (minString.empty() || compare(memo[l][i], minString)) { minString = memo[l][i]; } } smallAnswers.push_back(minString); } } static const string KEYWORD = "R1.R1.R1.R1.R1.R1."; int main() { int N; cin >> N; vector smallAnswers; createSmallAnswers(96 * 10, smallAnswers); vector prefixes; vector surfixes; for (int i = 96 * 9; i < 96 * 10; ++i){ const string& smallAnswer = smallAnswers[i]; const int offset = smallAnswer.find(KEYWORD); prefixes.push_back(smallAnswer.substr(0, offset)); surfixes.push_back(smallAnswer.substr(offset + KEYWORD.size())); } for (string in; cin >> in && N--;){ const int length = parse(in); if (length < 96 * 3){ cout << smallAnswers[length] << endl; } else { const int loop = length / 96 - 3; const int index = length % 96; cout << prefixes[index]; for (int i = 0; i < loop; ++i){ cout << "R1."; } cout << surfixes[index] << endl; } } }