Advertisement
GerONSo

Untitled

Jan 19th, 2020
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.29 KB | None | 0 0
  1. /*
  2.  
  3. ∧_∧
  4. ( ・ω・。)つ━☆・*。
  5. ⊂  ノ    ・゜
  6. しーJ   Accepted
  7.  
  8. */
  9.  
  10.  
  11.  
  12. // #pragma GCC optimize("O3")
  13. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  14.  
  15. #include <bits/stdc++.h>
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp>
  18.  
  19. #define ll long long
  20. #define all(x) begin(x), end(x)
  21. #define x first
  22. #define y second
  23. #define int long long
  24.  
  25. using namespace std;
  26. using namespace __gnu_pbds;
  27.  
  28. typedef long double ld;
  29. template<typename T>
  30. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  31.  
  32. const ld PI = atan2(0, -1);
  33.  
  34. void seriy() {
  35. ios::sync_with_stdio(0);
  36. cin.tie(0);
  37. cout.tie(0);
  38. cout << fixed << setprecision(14);
  39. #ifdef _offline
  40. freopen("input.txt", "r", stdin);
  41. freopen("output.txt", "w", stdout);
  42. #endif
  43. }
  44.  
  45. const int MAXN = 1e6 + 10;
  46. const int MAXM = 600;
  47. const int INF = 1e18 + 7;
  48. const int BASE = 47;
  49. const int MOD = 1e9 + 7;
  50. const int MAXLOG = 61;
  51. const ld EPS = 1e-6;
  52.  
  53. string out(int n, string c) {
  54. string k = "";
  55. for(int i = 0; i < n - 1; i++) {
  56. k += c + "*";
  57. }
  58. k += c;
  59. return k;
  60. }
  61.  
  62. signed main() {
  63. seriy();
  64. // cerr << (1ll << 59) - 2 << " ";
  65. string ans = "";
  66. string ans2;
  67. ans2.resize(1001);
  68. int n, d;
  69. cin >> n >> d;
  70. int nn = n;
  71. string k;
  72. k += (d + '0');
  73. if(n % d == 0) {
  74. if(d != 1) {
  75. vector<int> pw;
  76. pw.push_back(1);
  77. while(pw.back() <= 1e18) {
  78. pw.push_back(pw.back() * d);
  79. }
  80. int cur = 0;
  81. for(int i = pw.size() - 1; i > 0; i--) {
  82. if(n >= pw[i]) {
  83. n -= pw[i];
  84. cur += pw[i];
  85. ans += out(i, k);
  86. if(n != 0) {
  87. ans += "+";
  88. }
  89. }
  90. else {
  91. int now = cur + pw[i];
  92. int diff = now - nn;
  93. string succ = "";
  94. succ += out(i, k);
  95. for(int j = i; j > 0; j--) {
  96. if(diff >= pw[j]) {
  97. diff -= pw[j];
  98. succ += "-";
  99. succ += out(j, k);
  100. }
  101. }
  102. // cerr << now << " " << succ << '\n';
  103. if(ans.size() + succ.size() < ans2.size()) {
  104. ans2 = ans;
  105. if(ans.size() != 0) ans2 += "+";
  106. ans2 += succ;
  107. }
  108. }
  109. }
  110. }
  111. else {
  112. if(n < 1e6) {
  113. for(int i = 0; i < n - 1; i++) {
  114. ans += "1+";
  115. ans2 += "1+";
  116. }
  117. ans += "1";
  118. ans2 += "1";
  119. }
  120. }
  121. }
  122. else {
  123. ans = "no solution";
  124. ans2 = "no solution";
  125. }
  126. // assert(ans.size() <= 1000 || d == 1);
  127. if(ans2.size() <= 1000) cout << ans2;
  128. else if(ans.size() <= 1000) cout << ans;
  129. else cout << "no solution";
  130. return 0;
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement