Advertisement
MegaVerkruzo

Untitled

Sep 9th, 2019
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.40 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <map>
  6.  
  7. using namespace std;
  8.  
  9. bool lest(vector<int>& a, vector<int>& b, map<int, int> b_map, int n, long long& c_num, vector<int>& c, int i, int coun) {
  10. if (coun == 0) {
  11. return true;
  12. }
  13. if (b_map[c[i] - a[i] - b[i]] > 0) {
  14. b_map[c[i] - a[i] - b[i]]--;
  15. b[i] = c[i] - a[i] - b[i];
  16. coun--;
  17. if (lest(a, b, b_map, n, c_num, c, i + 1, coun)) {
  18. return true;
  19. }
  20. }
  21. else if (b_map[c[i] - a[i] + 10 - b[i]] > 0) {
  22. b_map[c[i] - a[i] + 10 - b[i]]--;
  23. b[i] = c[i] - a[i] + 10 - b[i];
  24. b[i + 1] = 1;
  25. coun--;
  26. if (lest(a, b, b_map, n, c_num, c, i + 1, coun)) {
  27. return true;
  28. }
  29. }
  30. return false;
  31. }
  32.  
  33. int main()
  34. {
  35. string x, y, z;
  36. cin >> x >> y >> z;
  37. long long c_num = 0, coun = 0;
  38. int n = max(x.length(), max(y.length(), z.length()));
  39. n++;
  40. vector<int> a(x.length(), 0), b(n, 0), c(n, 0);
  41. map<int, int> b_map;
  42. for (int i = 0; i < x.length(); ++i) {
  43. a[i] = x[x.length() - i - 1] - '0';
  44. }
  45. sort(a.begin(), a.end());
  46. for (int i = 0; i < y.length(); ++i) {
  47. b_map[y[i] - '0']++;
  48. coun++;
  49. }
  50. for (int i = 0; i < z.length(); ++i) {
  51. c[i] = z[z.length() - i - 1] - '0';
  52. c_num = c_num * 10 + z[i] - '0';
  53. }
  54. int x_ans = -1, y_ans = -1;
  55. do {
  56. reverse(a.begin(), a.end());
  57. a.push_back(0);
  58. if (lest(a, b, b_map, n, c_num, c, 0, coun)) {
  59. reverse(a.begin(), a.end());
  60. long long ans_x = 0;
  61. for (int i = 0; i < a.size(); ++i) {
  62. ans_x = ans_x * 10 + a[i];
  63. }
  64. reverse(a.begin(), a.end());
  65. long long ans_y = 0;
  66. reverse(b.begin(), b.end());
  67. for (int i = 0; i < b.size(); ++i) {
  68. ans_y = ans_y * 10 + b[i];
  69. }
  70. if (x_ans == -1 || x_ans > ans_x) {
  71. x_ans = ans_x;
  72. y_ans = ans_y;
  73. }
  74. }
  75. a.pop_back();
  76. reverse(a.begin(), a.end());
  77. b.clear();
  78. b.assign(n, 0);
  79. } while (next_permutation(a.begin(), a.end()));
  80. if (x_ans == -1) {
  81. cout << "NO";
  82. }
  83. else {
  84. cout << "YES\n" << x_ans << " " << y_ans;
  85. }
  86. return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement