#include #include inline int index_by_letter(char c) { int i = 0; switch (c) { case 'M': ++i; case 'D': ++i; case 'C': ++i; case 'L': ++i; case 'X': ++i; case 'V': ++i; } return i; } const int value_by_index[7] = {1, 5, 10, 50, 100, 500, 1000}; int count[7] = {0, 0, 0, 0, 0, 0, 0}; int solution[7] = {0, 0, 0, 0, 0, 0, 0}; const char *letter_by_index = "IVXLCDM"; int max_index = 6; int n; int input_value_without_max = 0; inline int calculate() { return solution[0] * value_by_index[0] + solution[1] * value_by_index[1] + solution[2] * value_by_index[2] + solution[3] * value_by_index[3] + solution[4] * value_by_index[4] + solution[5] * value_by_index[5] + solution[6] * value_by_index[6]; } bool solve(int current_depth) { if (++current_depth == max_index) { return n + input_value_without_max == 2 * calculate(); } for (int i = 0; i <= count[current_depth]; ++i) { solution[current_depth] = i; if (solve(current_depth)) { return true; } } return false; } int main() { std::string s; std::cin >> n >> s; for (auto c: s) { ++count[index_by_letter(c)]; } for (; max_index > 0 && !count[max_index]; --max_index); n -= count[max_index] * value_by_index[max_index]; for (int i = 0; i < max_index; input_value_without_max += value_by_index[i] * count[i], ++i); if (solve(-1)) { for (int i = max_index; i > 0; ) { --i; std::cout << std::string(count[i] - solution[i], letter_by_index[i]); } std::cout << std::string(count[max_index], letter_by_index[max_index]); for (int i = max_index; i > 0; ) { --i; std::cout << std::string(solution[i], letter_by_index[i]); } std::cout << std::endl; } else { std::cout << "NO" << std::endl; } return 0; }