JEDNAKOS - JEDNAKOST

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/jednakos


Trong khi đọc một quyển sách toán, Mirko nhận thấy có một số đẳng thức lạ dạng A=S. Điều kì lạ là đẳng thức này không đúng (A<>S). Mirko nhận thấy rằng cần phải thêm một số dấu cộng vào giữa 1 số cặp chữ số liên tiếp ở vế trái của đẳng thức. Bạn hãy tìm cách thêm vào ít nhất các dấu cộng vào vế trái của đẳng thức để đẳng thức trở nên đúng. Các số ở đẳng thức đúng có thể có các chữ số 0 vô nghĩa ở đầu.

Input

Gồm một dòng duy nhất chứa đẳng thức dạng A=S

A và S không có chữ số 0 vô nghĩa ở đầu. A<>S

A có nhiều nhất 1000 chữ số

S<=5000

Dữ liệu liên đảm bảo có kết quả

Output

Gồm một dòng duy nhất chứa số lượng dấu cộng ít nhất cần sử dụng

Example

Input:
143175=120

Output:
2
Input:
5025=30

Output:
1
Input:
999899=125

Output:
4


Added by:sieunhan
Date:2009-01-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Croatia regional competition 2008

hide comments
2023-04-09 17:11:33
Handle cases where are lots of zeros. This would lead to TLE.
2021-07-12 17:05:44
lol
00000000000000000000000000000000000000000000=0
ans will 0

[Simes]: this is an invalid test case. The problem states "A and S will both be positive integers without leading zeros."

Last edit: 2022-07-15 08:56:00
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.