Mã số thưởng (tổng chữ số)

Nguồn: CLUE OJ Độ khó: Dễ Xâu Tổng chữ số Số lớn

Đề bài

Nam thường xuyên tham gia thi lập trình trên mạng. Vì đạt được thành tích cao nên Nam được tặng một phần mềm diệt virus. Nhà sản xuất cung cấp cho Nam một mã số là số nguyên dương $N$ có không quá $2555$ chữ số. Để cài đặt phần mềm, Nam phải nhập mật khẩu là số nguyên dương $M$ bằng tổng các chữ số của $N$.

Hãy tìm $M$.

Dữ liệu vào:

Một dòng chứa số nguyên dương $N$ (không có chữ số $0$ ở đầu).

Kết quả:

In ra số nguyên dương $M$.

Giới hạn:

• $1 \le N < 10^{2555}$ (tức $N$ có từ $1$ đến $2555$ chữ số).

Subtask:

• Subtask 1 (30% số điểm): $N < 10^{18}$.
• Subtask 2 (70% 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

84915388247

Ví dụ 1 – output

59

• $8 + 4 + 9 + 1 + 5 + 3 + 8 + 8 + 2 + 4 + 7 = 59$.

Nguồn: phỏng theo bài "MÃ SỐ THƯỞNG" – vinhdinhcoder.net (chủ đề Xâu kí tự).

Lời mở đầu

Tính tổng chữ số thì quá quen: n % 10, n /= 10… nhưng ở đây $N$ có tới 2555 chữ số, không có kiểu số nào chứa nổi. Đổi góc nhìn một chút: coi $N$ là một xâu kí tự, mỗi kí tự là một chữ số. Ghi chú: đề gốc có một câu thừa ở đầu ("Xu đang dạy em Xốp học toán lớp một…", chép nhầm từ bài khác) – mình bỏ đi vì không liên quan.

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ưởngđọc dạng xâuLờ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. Có 20 test, đa số có hàng trăm tới 2555 chữ số.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2–5	Số có 1–2 chữ số, số lớn nhất của long long
6–7	Số 20 chữ số – vượt cả unsigned long long
8–9	$10^{2554}$ và số gồm 2555 chữ số 9 (tổng lớn nhất 22995 – vượt kiểu char)
10–20	Số ngẫu nhiên dài 19–2555 chữ số

Ý tưởngĐọc N vào xâu, cộng từng kí tự

Đọc $N$ bằng string n; cin >> n;. Khi đó n[i] là kí tự chữ số thứ $i$, và giá trị của nó là n[i] - '0' (mã ASCII của '0'…'9' đứng liền nhau).

Tổng chữ số thì nhỏ

$N$ thì khổng lồ, nhưng tổng chữ số tối đa chỉ $9 \times 2555 = 22995$ – biến int là thoải mái.

Em nhập mã số rồi bấm Tiếp để xem từng chữ số được cộng dồn:

n =

Ví dụ nhanh:

Lời giảiMột vòng lặp qua các kí tự

Chỉ cần đúng một ý: đọc vào xâu, không đọc vào biến số.

C++▶ Chạy tay từng dòng codeCộng giá trị của từng kí tự chữ số.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Nếu đọc $N$ có 2555 chữ số vào long long, cin sẽ báo lỗi và biến nhận giá trị sai – kết quả hỏng hoàn toàn.
2. Quên trừ '0' thì ta cộng mã ASCII ('0' là 48) chứ không phải chữ số.
3. Bản Python: int(c) đổi một kí tự chữ số thành số.

Không gian$O(|N|)$

Thời gian$O(|N|)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.017s. 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 $N$ vào long long	6/20	sai test 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20
Đọc $N$ vào unsigned long long	7/20	sai test 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20
Cộng n[i] mà quên trừ '0'	0/20	sai test 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Lưu tổng trong biến char	11/20	sai test 7, 9, 10, 12, 13, 14, 15, 18, 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.003s	Full điểm
	Python	20/20	0.017s	Full điểm
long long	C++	6/20	–	Mất 14 test
unsigned long long	C++	7/20	–	Mất 13 test
Quên trừ '0'	C++	0/20	–	Mất 20 test
Tổng kiểu char	C++	11/20	–	Mất 9 test

Ghi chú của mình: "số quá lớn thì đọc vào xâu" – câu thần chú mở đầu cho cả loạt bài số lớn. Tổng chữ số, chữ số cuối, kiểm tra chia hết cho 3, 9… đều làm được trực tiếp trên xâu.

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 😇