P1874 Fast Summation

2023-10-08 update: Added two hack cases. 2023-12-16 update: Added two hack cases.

Given a numeric string, make it equal to a given target number using the minimum number of additions. Each addition means inserting a plus sign at some position in the string. After all required plus signs are inserted, evaluate it as ordinary addition. For example, consider the string `12`. With $0$ additions, we get the number $12$. If we insert $1$ plus sign, we get $3$. Therefore, in this case, the minimum number of additions to obtain the number $3$ is $1$. Another example: consider the string `303` and the target number $6$. The optimal way is not `3+0+3`, but `3+03`. This works because a leading $0$ in a number does not change its value.

The first line: a string $s$. The second line: an integer $n$.

Output a single integer on one line, the minimum number of additions to make $s$ equal to $n$. If it is impossible to make $s$ equal to $n$, output $-1$.

Constraints For $100\%$ of the testdata, it is guaranteed that $1 \le \operatorname{len}(s) \le 40$, $1 \le n \le 10^5$. Translated by ChatGPT 5