https://www.luogu.com.cn/record/121846395

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string str;
int n, len, ans = 45, s[45];

void dfs(int dep, int pos, int sum)
{
    // cout << dep << " " << pos << " " << sum << "\n";
    if (pos >= len)
        return;
    int tmp = 0;
    for (int i = pos + 1; i <= len; i++)
        tmp = tmp * 10 + s[i];
    // cout << tmp << " ";
    if (sum + tmp == n)
    {
        ans = min(ans, dep + 1);
        return;
    }
    else if (sum + tmp < n)
        return;
    tmp = 0;
    for (int i = pos + 1; i <= len; i++)
        tmp += s[i];
    // cout << tmp << "\n" << ans << "\n\n";
    if (sum + tmp > n)
        return;
    dfs(dep, pos + 1, sum * 10 + s[pos + 1]);
    dfs(dep + 1, pos + 1, sum + s[pos + 1]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> str >> n;
    len = str.length();
    for (int i = 1; i <= len; i++)
        s[i] = str[i - 1] - '0';
    dfs(0, 1, s[1]);
    if (ans != 45)
        cout << ans << "\n";
    else
        cout << -1 << "\n";
    return 0;
}