Cộng hai số lớn

Nguồn: CLUE OJ Độ khó: Trung bình Xâu Số lớn (Big Int) Cộng tay

Đề bài

Với những số rất lớn, ví dụ $2\underbrace{00\ldots0}_{200\text{ chữ số } 0}$, các kiểu dữ liệu số đã học không thể lưu trữ được. Khi đó ta dùng xâu để lưu số; nhưng với xâu thì không thể dùng trực tiếp các phép toán số học.

Em hãy lập trình tính tổng của hai số nguyên lớn (Big Number) được nhập vào từ bàn phím.

Dữ liệu vào:

Gồm hai dòng, mỗi dòng là một số nguyên không âm.

Kết quả:

In ra tổng của hai số đó.

Giới hạn:

• Mỗi số có từ $1$ đến $10^6$ chữ số, không có chữ số $0$ vô nghĩa ở đầu (số $0$ được viết là 0).

Subtask:

• Subtask 1 (20% số điểm): mỗi số có không quá $18$ chữ số.
• Subtask 2 (30% số điểm): mỗi số có không quá $1000$ chữ số.
• Subtask 3 (50% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

55
30

Ví dụ 1 – output

85

Ví dụ 2 – input

9999999999999999999
1

Ví dụ 2 – output

10000000000000000000

• Ví dụ 2: tổng có 20 chữ số, vượt khỏi kiểu long long (và cả unsigned long long).

Nguồn: phỏng theo bài "BIG NUMBER" – vinhdinhcoder.net (chủ đề Xâu kí tự).

Lời mở đầu

Số có tới một triệu chữ số thì không kiểu số nào chứa nổi – cả unsigned long long cũng chỉ tới khoảng $1{,}8 \cdot 10^{19}$. Cách duy nhất là lưu số dưới dạng xâu và tự làm phép cộng y như cộng tay hồi lớp 2: cộng từ hàng đơn vị, có nhớ.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngcộng có nhớLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Test 1–10 là số ngắn (tới vài nghìn chữ số), test 11–20 là số tới $10^6$ chữ số.

Test	Nội dung kiểm tra
1–4	Ví dụ của đề, $0 + 0$, nhớ sinh thêm một chữ số ở đầu
5, 9	Kết quả vượt unsigned long long
6–8, 10	Hai số dài khác nhau, có số 0
11–20	Số tới $10^6$ chữ số, toàn chữ số 9 (nhớ lan suốt cả số) – chèn chữ số vào đầu xâu sẽ quá thời gian

Ý tưởngCộng từ phải sang trái như cộng tay

Đặt hai số thẳng hàng theo hàng đơn vị. Dùng hai chỉ số $i, j$ chạy từ cuối mỗi xâu về đầu và biến nho (0 hoặc 1):

• tổng một hàng: s = nho + a[i] + b[j] (xâu nào đã hết chữ số thì coi là 0);
• chữ số kết quả của hàng là s % 10, nhớ sang hàng sau là s / 10.

Lặp khi còn chữ số ở một trong hai xâu hoặc còn nhớ – điều kiện "còn nhớ" giúp ra chữ số 1 ở đầu khi $999 + 1 = 1000$.

Thêm vào cuối rồi đảo ngược

Ta tìm ra chữ số kết quả theo thứ tự từ hàng đơn vị lên, tức là ngược. Nếu mỗi lần chèn vào đầu xâu (kq = c + kq) thì phải chép lại cả xâu – $10^6$ lần như vậy là quá chậm. Hãy push_back vào cuối, xong xuôi thì reverse một lần.

Em nhập hai số rồi bấm Tiếp để xem phép cộng từng hàng:

a = b =

Ví dụ nhanh:

Lời giảiCộng có nhớ, đẩy vào cuối rồi đảo ngược

Bản C++ cộng từng chữ số. Bản Python cũng phải tự cộng vì Python đổi một xâu triệu chữ số sang số nguyên rất chậm (và mặc định bị giới hạn 4300 chữ số); để nhanh, mình cộng theo từng khúc 18 chữ số – mỗi khúc vẫn là phép cộng có nhớ, chỉ là "chữ số" lớn hơn.

C++▶ Chạy tay từng dòng codeCộng từ cuối hai xâu về đầu, có biến nhớ.

Dữ liệu vào (stdin) – sửa thoải mái55 30

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. a[i] - '0' đổi kí tự chữ số thành số; '0' + s % 10 đổi ngược lại.
2. Điều kiện nho > 0 trong vòng while giúp in ra chữ số 1 ở đầu khi tổng dài hơn cả hai số.
3. Đoạn "bỏ số 0 ở đầu" chỉ có tác dụng với $0 + 0$; nhờ p + 1 < kq.size() ta luôn giữ lại ít nhất một chữ số.

Không gian$O(\max(|a|, |b|))$

Thời gian$O(\max(|a|, |b|))$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.044s. Bản Python đúng 20/20 test, chạy lâu nhất 0.072s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Đọc vào unsigned long long rồi cộng	5/20	sai test 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Quên chữ số nhớ ở hàng cao nhất (thiếu || nho > 0)	11/20	sai test 2, 3, 6, 9, 11, 12, 13, 14, 17
Chèn chữ số vào đầu xâu: kq = c + kq	11/20	sai test 11, 12, 13, 14, 15, 16, 17, 18, 20
Chỉ cộng phần dài bằng số ngắn hơn	8/20	sai test 2, 5, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.044s	Full điểm
	Python	20/20	0.072s	Full điểm
unsigned long long	C++	5/20	–	Mất 15 test
Quên nhớ cuối	C++	11/20	–	Mất 9 test
Chèn vào đầu xâu	C++	11/20	–	Mất 9 test
Bỏ phần thừa	C++	8/20	–	Mất 12 test

Ghi chú của mình: phép cộng số lớn là viên gạch đầu tiên của chuyên đề "số nguyên lớn" (Big Int). Trừ, nhân số lớn với số nhỏ… cũng làm theo đúng tinh thần "cộng tay": duyệt từ hàng đơn vị, giữ biến nhớ.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇