JEDNAKOS  JEDNAKOST
English  Vietnamese 
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.
Input
The first line contains the equation in the form A=S.
A and S will both be positive integers without leading zeros. They will be different.
A will contain at most 1000 digit
S will be less than or equal to 5000
Note: The input data will guarantee that a solution, although not necessarily unique, will always exist.
Output
Output the number of addition operations needed
Example
Input: 143175=120 Output: 2
Input: 5025=30 Output: 1
Input: 999899=125 Output: 4
hide comments
kmkhan_014:
20180511 22:19:09
Century!


abhishek_8:
20180219 11:50:47
100100400300040103040=318


mastik5h_1998:
20171018 03:27:59
try to eliminate zeros at left side to achieve ac.


phanduy16:
20170820 05:45:23
I passed all test cases by COCI, and got runtime error (SIGSEGV) here @@ Last edit: 20170820 15:14:30 

omartarek32:
20160828 13:12:46
tle with java , I think this judge put one time for all languages . I'm sure from the solution , and this not the first problem that I have met this problem 

gasser:
20160422 13:38:41
if there is test case:


naruto09:
20151230 10:58:35
Last edit: 20151230 12:06:35 

topke:
20151130 14:00:04
Care about ending zeros caused me a lot of WA. All in all not hard problem except that small corner case. 

Sarthak Munshi:
20151010 18:52:30
11th case = TLE ! 

rajbir:
20150217 19:40:38
nice one

Added by:  sieunhan 
Date:  20090121 
Time limit:  0.145s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource:  Croatia regional competition 2008 