Pasted

#include <iostream>
#include <string>
 
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;
}