fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 121;
  5. const int LIM = 1000001;
  6.  
  7. string s, n;
  8. bool PLUS[MAX];
  9. bitset<LIM> dp[MAX];
  10. bitset<LIM> vis[MAX];
  11.  
  12. bool solve(int idx, int rem) {
  13.   if (idx == s.length()) {
  14.     return rem == 0;
  15.   }
  16.   if (vis[idx][rem]) {
  17.     return dp[idx][rem];
  18.   }
  19.   vis[idx][rem] = 1;
  20.   int x = 0;
  21.   for(int i = idx; i < s.length(); ++i) {
  22.     x = x * 10 + s[i] - '0';
  23.     if (x > rem) {
  24.       break;
  25.     }
  26.     if (solve(i + 1, rem - x)) {
  27.       PLUS[i] = 1;
  28.       return (dp[idx][rem] = 1);
  29.     }
  30.   }
  31.   return (dp[idx][rem] = 0);
  32. }
  33.  
  34. int main() {
  35.   int t;
  36.   cin >> t;
  37.   while(t--) {
  38.     cin >> s >> n;
  39.     int N = 0;
  40.     for(int i = 0; i < n.length(); ++i) {
  41.       N = N * 10 + n[i] - '0';
  42.     }
  43.     for(int i = 0; i < s.length(); ++i) {
  44.       PLUS[i] = 0;
  45.       for(int j = 0; j <= N; ++j) {
  46.         dp[i][j] = 0;
  47.         vis[i][j] = 0;
  48.       }
  49.     }
  50.     bool get = solve(0, N);
  51.     for(int i = 0; i < s.length(); ++i) {
  52.       if (i && PLUS[i-1]) {
  53.         cout << "+";
  54.       }
  55.       cout << s[i];
  56.     }
  57.     cout << "\n";
  58.   }
  59.   return 0;
  60. }
Success #stdin #stdout 0s 4248KB
comments (?)
stdin
copy 
4
120012 33
15112 28
123 123
15489001 10549
stdout
copy 
1+20+0+12
15+1+12
123
1548+9001
https://ideone.com/5rU7XN
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!