trang chủ / đề bài / icpc22_mn_l

Phép cộng

Đề bài

Mô tả

Long là một cậu bé 6 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 n, số cột chữ số của phép cộng.
  • Mỗi dòng trong 3 dòng tiếp theo chứa một xâu gồm n 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ố 0, 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

  • 1≤n≤1000.
  • Tổng các giá trị n trong một file không vượt quá 106.

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 122+238=360. 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ì 91+12=103 có ba chữ số, không khớp với 03. Xoá cột thứ nhất được 1+2=3.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0