aydarbiktimirov

Untitled

Oct 12th, 2012
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.81 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3.  
  4. inline int index_by_letter(char c)
  5. {
  6.     int i = 0;
  7.     switch (c)
  8.     {
  9.         case 'M':
  10.             ++i;
  11.         case 'D':
  12.             ++i;
  13.         case 'C':
  14.             ++i;
  15.         case 'L':
  16.             ++i;
  17.         case 'X':
  18.             ++i;
  19.         case 'V':
  20.             ++i;
  21.     }
  22.     return i;
  23. }
  24.  
  25. const int value_by_index[7] = {1, 5, 10, 50, 100, 500, 1000};
  26. int count[7] = {0, 0, 0, 0, 0, 0, 0};
  27. int solution[7] = {0, 0, 0, 0, 0, 0, 0};
  28. const char *letter_by_index = "IVXLCDM";
  29. int max_index = 6;
  30. int n;
  31. int input_value_without_max = 0;
  32.  
  33. inline int calculate()
  34. {
  35.     return solution[0] * value_by_index[0] + solution[1] * value_by_index[1] + solution[2] * value_by_index[2] +
  36.         solution[3] * value_by_index[3] + solution[4] * value_by_index[4] + solution[5] * value_by_index[5] + solution[6] * value_by_index[6];
  37. }
  38.  
  39. bool solve(int current_depth)
  40. {
  41.     if (++current_depth == max_index)
  42.     {
  43.         return n + input_value_without_max == 2 * calculate();
  44.     }
  45.     for (int i = 0; i <= count[current_depth]; ++i)
  46.     {
  47.         solution[current_depth] = i;
  48.         if (solve(current_depth))
  49.         {
  50.             return true;
  51.         }
  52.     }
  53.     return false;
  54. }
  55.  
  56. int main()
  57. {
  58.     std::string s;
  59.     std::cin >> n >> s;
  60.     for (auto c: s)
  61.     {
  62.         ++count[index_by_letter(c)];
  63.     }
  64.     for (; max_index > 0 && !count[max_index]; --max_index);
  65.     n -= count[max_index] * value_by_index[max_index];
  66.     for (int i = 0; i < max_index; input_value_without_max += value_by_index[i] * count[i], ++i);
  67.     if (solve(-1))
  68.     {
  69.         for (int i = max_index; i > 0; )
  70.         {
  71.             --i;
  72.             std::cout << std::string(count[i] - solution[i], letter_by_index[i]);
  73.         }
  74.         std::cout << std::string(count[max_index], letter_by_index[max_index]);
  75.         for (int i = max_index; i > 0; )
  76.         {
  77.             --i;
  78.             std::cout << std::string(solution[i], letter_by_index[i]);
  79.         }
  80.         std::cout << std::endl;
  81.     }
  82.     else
  83.     {
  84.         std::cout << "NO" << std::endl;
  85.     }
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment