Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment