tien_noob

EXP

Aug 11th, 2021
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.64 KB | None | 0 0
  1. //Make CSP great again
  2. #include <bits/stdc++.h>
  3. #define TASK "EXP"
  4. using namespace std;
  5. string a, b;
  6. int n;
  7. vector<int> res;
  8. bool add[101];
  9. void read()
  10. {
  11.     cin >> a >> b;
  12.     n = a.length();
  13. }
  14. void Update(int mask)
  15. {
  16.     vector<int> p = {-1};
  17.     for (int j = 0; j < n; ++ j)
  18.     {
  19.         if (mask & (1 << j))
  20.         {
  21.             p.push_back(j);
  22.         }
  23.     }
  24.     long long sum = 0;
  25.     p.push_back(n - 1);
  26.     for (int k = 1; k < p.size(); ++ k)
  27.     {
  28.         long long fuck = 0;
  29.         for (int i = p[k - 1] + 1; i <= p[k]; ++ i)
  30.         {
  31.             fuck = fuck * 10 + a[i] - '0';
  32.         }
  33.         sum += fuck;
  34.     }
  35.     if (to_string(sum) == b)
  36.     {
  37.         res = p;
  38.     }
  39. }
  40. void Sub2()
  41. {
  42.     if (a == b)
  43.     {
  44.         cout << a;
  45.         return ;
  46.     }
  47.     for (int i = 1; i < 1 << (n - 1); ++ i)
  48.     {
  49.         Update(i);
  50.     }
  51.     for (int i = 1; i < res.size() - 1; ++ i)
  52.     {
  53.         add[res[i]] = true;
  54.     }
  55.     for (int i = 0; i < n; ++ i)
  56.     {
  57.         cout << a[i];
  58.         if (add[i])
  59.         {
  60.             cout << "+";
  61.         }
  62.     }
  63. }
  64. const int N = 1e5;
  65. int dp[101][N + 1];
  66. pair<int, int> Trace[101][N + 1];
  67. void Traceback(int i, int num)
  68. {
  69.     if (i == 0)
  70.     {
  71.         return ;
  72.     }
  73.     add[Trace[i][num].first] = true;
  74.     Traceback(Trace[i][num].first, num - Trace[i][num].second);
  75. }
  76. void Sub3()
  77. {
  78.     a = '?' + a;
  79.     dp[0][0] = 1;
  80.     for (int i = 1; i <= n; ++ i)
  81.     {
  82.         int sum = 0;
  83.         for (int j = i; j >= 1; -- j)
  84.         {
  85.             sum += (a[j] - '0') * pow(10, i - j);
  86.             if (sum >= N)
  87.             {
  88.                 break;
  89.             }
  90.             for (int k = 0; k + sum <= N; ++ k)
  91.             {
  92.                 if (dp[j - 1][k] == 1)
  93.                 {
  94.                     dp[i][k + sum] = 1;
  95.                     Trace[i][k + sum] = {j - 1, sum};
  96.                 }
  97.             }
  98.         }
  99.     }
  100.     int need = 0;
  101.     for (int i = 0; i < b.length(); ++ i)
  102.     {
  103.         need += pow(10, b.length() - i - 1) * (b[i] - '0');
  104.     }
  105.     Traceback(n, need);
  106.     for (int i = 1; i <= n; ++ i)
  107.     {
  108.         cout << a[i];
  109.         if (add[i])
  110.         {
  111.             cout << "+";
  112.         }
  113.     }
  114. }
  115. void solve()
  116. {
  117.     if (n <= 20)
  118.     {
  119.         Sub2(); return ;
  120.     }
  121.     Sub3();
  122. }
  123. int main()
  124. {
  125.     ios_base::sync_with_stdio(false);
  126.     cin.tie(nullptr);
  127.     freopen(TASK".INP", "r", stdin);
  128.     freopen(TASK".OUT", "w", stdout);
  129.     int t = 1;
  130.     bool typetest = false;
  131.     if (typetest)
  132.     {
  133.         cin >> t;
  134.     }
  135.     for (int __ = 1; __ <= t; ++ __)
  136.     {
  137.         read();
  138.         solve();
  139.     }
  140. }
  141.  
Add Comment
Please, Sign In to add comment