fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. vector<vector<int>> dp;
  5.  
  6. /*
  7.   we can use dynamic programming to solve this problem.
  8.   Observation: Any number in the final expression cannot have more than four 
  9.   digits because the maximum value of y is 5000. 
  10.   example:
  11.   x = 12341020
  12.   solve("12341020", y, 0):
  13.     choices for current state: 1, 12, 123, 1234
  14.   
  15.   Time Complexity: O(n * y)
  16.   n is length of x
  17.   Space Complexity: O(n * y)
  18. */
  19.  
  20. int solve(string &x, int y, int idx) {
  21.   if (y < 0) return 1000;
  22.   if (idx == x.length()) return (y == 0 ? 0 : 1000);
  23.  
  24.   if (dp[idx][y] != -1) return dp[idx][y];
  25.  
  26.   int ans = 1000;
  27.   for (int i = idx; i < min(idx + 4, (int )x.length()); i++) {
  28.     // stoi function converts string to integer
  29.     int num = stoi(x.substr(idx, i - idx + 1));
  30.  
  31.     ans = min(ans, solve(x, y - num, i + 1) + (i < x.length() - 1));
  32.     // not counting plus operator for the last number by checking (i < x.length() - 1)
  33.   }
  34.  
  35.   return dp[idx][y] = ans;
  36. } 
  37.  
  38. int main() {
  39.   string x; cin >> x;
  40.   int y; cin >> y;
  41.   int n = x.length();
  42.   dp = vector<vector<int>> (n, vector<int> (y + 1, -1));
  43.   int ans = solve(x, y, 0);
  44.   if (ans == 1000) cout << -1;
  45.   else cout << ans;
  46.   return 0;
  47. }
Success #stdin #stdout 0.01s 5360KB
comments (?)
stdin
copy 
111
12
stdout
copy 
1
https://ideone.com/Vcoz4B
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

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!