Phép cộng
Đề bài
Mô tả
Long là một cậu bé tuổi đang học phép cộng theo cột nhiều chữ số. Cậu thường thực hiện phép cộng hai số nguyên như sau:
321
+ 456
777
Đôi khi Long cộng sai, và bây giờ bạn cần giúp cậu trước khi nộp bài cho cô giáo. Vì Long đã viết phép cộng vào vở, bạn chỉ có thể xoá một số cột của phép cộng để phần còn lại trở thành một phép cộng đúng. Ví dụ, với phép cộng dưới đây, ta có thể được một phép cộng đúng bằng cách xoá cột thứ nhất và cột thứ tư.
71212 122
+ 12348 → + 238
93650 360
Hãy tìm số cột ít nhất cần xoá để các cột còn lại tạo thành một phép cộng đúng.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test.
- Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên , số cột chữ số của phép cộng.
- Mỗi dòng trong dòng tiếp theo chứa một xâu gồm chữ số. Số ở dòng thứ ba là tổng (không nhất thiết đúng) của hai số ở dòng thứ nhất và dòng thứ hai.
Dữ liệu kết thúc bằng một dòng chứa số , dòng này không cần xử lý.
Dữ liệu ra
Với mỗi bộ test, in ra một dòng chứa số cột ít nhất cần xoá.
Ràng buộc
- .
- Tổng các giá trị trong một file không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 321 456 777 5 71212 12348 93650 2 24 32 32 5 12299 12299 25598 0 |
0 2 2 1 |
Bộ thứ hai: xoá cột thứ nhất và cột thứ tư được . Bộ thứ ba: phải xoá cả hai cột. |
| 2 91 12 03 0 |
1 | Ví dụ bổ sung (không có trong đề gốc). Giữ cả hai cột thì có ba chữ số, không khớp với . Xoá cột thứ nhất được . |
Bình luận