Jednakost

[Charlz_Klug]

Есть задача. Суть такова: есть выражение вида $A = B$, где $A$ и $B$ - некоторые числа. Нужно разработать алгоритм определяющий каково минимальное количество нулей, которые нужно вставить между цифрами $A$ чтобы обратить выражение в равенство. Строки вида "$0xxx$" рассматривать как "$xxx$". Максимальное количество символов в $A$ равно $1000$, $B$ не больше $5000$.
Пример: $143175=120$. Здесь минимальное количество плюсов $2$, т.е. $14+31+75=120$.
Ещё пример: $5025=30$. Ответ: $1$, т.е. $5+025 = 5+25 = 30$.
Ещё пример: $999899=125$. Ответ: $4$: $9 + 9 + 9 + 89 + 9 = 125$.
Я долго думал, но ничего кроме перебора не придумал. Но перебор крайне долгая операция. Прошу подсказок.

Оригинальная формулировка:
While browsing a math book, Mirko found a strange equation of the form A=S.What makes the equation strange is that A and S are not the same,which makes the equation incorrect. Mirko realized that the left side of the equation should have addition operations between some pairs of digits in A. Write a program that inserts the smallest number of addition operations on the left side to make the equation correct. The numbers in the corrected equation may contain arbitrary amounts of eading zeros.

[Pphantom]

Charlz_Klug в сообщении #1481294 писал(а):

Пример: $143175=120$. Здесь минимальное количество нулей $2$, т.е. $14+31+75=120$.

А почему символ $+$ вы называете "нулем"?

[Charlz_Klug]

Спасибо за замечание! Поправил.

[Lia]

Charlz_Klug
Лучше приведите формулировку из ссылки: Ваша интерпретация совершенно непонятна.

[Charlz_Klug]

Добавил оригинальную формулировку.

[mihaild]

[надо как-то более явно написать, что $B < 5000$, а не количество символов меньше $5000$, а то я долго думал над, видимо, более сложной задачей]
Charlz_Klug, представьте, что вы решили поставить последний плюс на $i$-й позиции. Как выглядит задача по оптимальной расстановке остальных плюсов?

[svv]

Charlz_Klug в сообщении #1481296 писал(а):

Спасибо за замечание! Поправил.

Не всё!

Charlz_Klug в сообщении #1481294 писал(а):

каково минимальное количество нулей, которые нужно вставить между цифрами $A$

Charlz_Klug в сообщении #1481302 писал(а):

Добавил оригинальную формулировку.

Не всю! Разве это, например, не имеет значения?:

Цитата:

Note: The input data will guarantee that a solution, although not necessarily unique, will always exist.

Charlz_Klug в сообщении #1481294 писал(а):

eading zeros

leading? ending?

[mihaild]

svv в сообщении #1481311 писал(а):

Разве это, например, не имеет значения?

На самом деле нет. По крайней мере я не могу придумать алгоритм, который быстро находит число плюсов, если решение есть, и делает что-то не то, если решения нет.