Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Make CSP great again
- #include <bits/stdc++.h>
- #define TASK "EXP"
- using namespace std;
- string a, b;
- int n;
- vector<int> res;
- bool add[101];
- void read()
- {
- cin >> a >> b;
- n = a.length();
- }
- void Update(int mask)
- {
- vector<int> p = {-1};
- for (int j = 0; j < n; ++ j)
- {
- if (mask & (1 << j))
- {
- p.push_back(j);
- }
- }
- long long sum = 0;
- p.push_back(n - 1);
- for (int k = 1; k < p.size(); ++ k)
- {
- long long fuck = 0;
- for (int i = p[k - 1] + 1; i <= p[k]; ++ i)
- {
- fuck = fuck * 10 + a[i] - '0';
- }
- sum += fuck;
- }
- if (to_string(sum) == b)
- {
- res = p;
- }
- }
- void Sub2()
- {
- if (a == b)
- {
- cout << a;
- return ;
- }
- for (int i = 1; i < 1 << (n - 1); ++ i)
- {
- Update(i);
- }
- for (int i = 1; i < res.size() - 1; ++ i)
- {
- add[res[i]] = true;
- }
- for (int i = 0; i < n; ++ i)
- {
- cout << a[i];
- if (add[i])
- {
- cout << "+";
- }
- }
- }
- const int N = 1e5;
- int dp[101][N + 1];
- pair<int, int> Trace[101][N + 1];
- void Traceback(int i, int num)
- {
- if (i == 0)
- {
- return ;
- }
- add[Trace[i][num].first] = true;
- Traceback(Trace[i][num].first, num - Trace[i][num].second);
- }
- void Sub3()
- {
- a = '?' + a;
- dp[0][0] = 1;
- for (int i = 1; i <= n; ++ i)
- {
- int sum = 0;
- for (int j = i; j >= 1; -- j)
- {
- sum += (a[j] - '0') * pow(10, i - j);
- if (sum >= N)
- {
- break;
- }
- for (int k = 0; k + sum <= N; ++ k)
- {
- if (dp[j - 1][k] == 1)
- {
- dp[i][k + sum] = 1;
- Trace[i][k + sum] = {j - 1, sum};
- }
- }
- }
- }
- int need = 0;
- for (int i = 0; i < b.length(); ++ i)
- {
- need += pow(10, b.length() - i - 1) * (b[i] - '0');
- }
- Traceback(n, need);
- for (int i = 1; i <= n; ++ i)
- {
- cout << a[i];
- if (add[i])
- {
- cout << "+";
- }
- }
- }
- void solve()
- {
- if (n <= 20)
- {
- Sub2(); return ;
- }
- Sub3();
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- freopen(TASK".INP", "r", stdin);
- freopen(TASK".OUT", "w", stdout);
- int t = 1;
- bool typetest = false;
- if (typetest)
- {
- cin >> t;
- }
- for (int __ = 1; __ <= t; ++ __)
- {
- read();
- solve();
- }
- }
Add Comment
Please, Sign In to add comment