Phát kẹo

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp Kiểu dữ liệu

Đề bài

Thầy Phú phát kẹo cho $N$ học sinh trong lớp theo quy tắc: em đầu tiên nhận $1$ viên kẹo, mỗi em tiếp theo nhận nhiều hơn em trước $3$ viên (tức là $1, 4, 7, 10, \ldots$). Hỏi thầy cần chuẩn bị tổng cộng bao nhiêu viên kẹo?

Dữ liệu vào:

Một số nguyên $N$ là số học sinh.

Kết quả:

Tổng số viên kẹo cần chuẩn bị. Nếu $N = 0$ thì in ra $0$.

Giới hạn:

• $0 \le N \le 45\,000$

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

1

Ví dụ 1 – output

1

Ví dụ 2 – input

2

Ví dụ 2 – output

5

• Ví dụ 1: chỉ có một em, nhận $1$ viên.
• Ví dụ 2: em thứ nhất nhận $1$ viên, em thứ hai nhận $1 + 3 = 4$ viên; tổng $5$ viên.

Nguồn: phỏng theo bài "PHÁT KẸO" – vinhdinhcoder.net (chủ đề Lặp FOR).

Lời mở đầu

Mỗi em nhận nhiều hơn em trước 3 viên: $1, 4, 7, 10, \ldots$ Dùng vòng lặp "phát" lần lượt cho từng em và cộng dồn là ra tổng. Cái bẫy là tổng có thể vượt 2 tỉ (với $N = 45\,000$ là hơn 3 tỉ viên), và trường hợp lớp không có học sinh nào ($N = 0$). Ghi chú: đề gốc cho $N = 0$ nhưng không nói in gì; mình ghi rõ trong đề là in 0.

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 dồnLờ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. Mọi test có $0 \le N \le 45\,000$.

Test	Nội dung kiểm tra
1–8	Ví dụ đề, $N = 0$ (test 3), $N$ nhỏ tới 1000
9–10	$N = 26\,755$ / $26\,756$: ranh giới tràn int của biểu thức $N \cdot (3N - 1)$ (cách dùng công thức)
12–13	$N = 37\,837$ / $37\,838$: ranh giới tổng kẹo vượt $2\,147\,483\,647$
11, 14–20	$N$ lớn tới $45\,000$: tổng tới hơn 3 tỉ

Ý tưởngPhát lần lượt từng em, cộng dồn

Dùng hai biến: keo – số kẹo em hiện tại nhận (ban đầu 1), tong – tổng đã phát (ban đầu 0). Lặp $N$ lần, mỗi lần:

• tong += keo (phát cho em này);
• keo += 3 (em sau nhận nhiều hơn 3 viên).

Với $N = 0$ vòng lặp for không chạy lần nào, tong giữ nguyên 0 – đúng yêu cầu, không cần xử lý riêng.

Chọn kiểu dữ liệu

Em thứ $N$ nhận $3N - 2$ viên, tổng là $\dfrac{N(3N - 1)}{2}$. Với $N = 45\,000$: tổng $= 3\,037\,477\,500$ – lớn hơn giới hạn int ($2\,147\,483\,647$) → tong phải là long long.

Em nhập số học sinh $N$ rồi bấm Tiếp để xem thầy phát kẹo cho từng em:

N =

Ví dụ nhanh:

Lời giảiVòng lặp for với tong kiểu long long

Đúng như ý tưởng: lặp $N$ lần, mỗi lần cộng keo vào tong rồi tăng keo thêm 3.

C++▶ Chạy tay từng dòng codeLặp N lần: cộng số kẹo của em hiện tại vào tổng, rồi tăng thêm 3 cho em sau.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Sau 8 lần lặp, phần còn lại được "tua nhanh" trong một bước.

1. Biến đếm i chỉ dùng để lặp đủ $N$ lần; số kẹo được giữ riêng trong biến keo. (Cũng có thể tính trực tiếp em thứ $i$ nhận $3i - 2$ viên.)
2. Công thức $\dfrac{N(3N - 1)}{2}$ cũng cho kết quả ngay, nhưng phải tính bằng long long: n * (3 * n - 1) với n kiểu int tràn từ $N = 26\,756$.
3. Python: for i in range(n) lặp đúng $n$ lần (không lần nào khi $n = 0$).

Không gian$O(1)$

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.007s. Bản Python đúng 20/20 test, chạy lâu nhất 0.037s. 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ú
Tổng kiểu int	15/20	sai test 13, 14, 15, 16, 19
Công thức n * (3 * n - 1) / 2 với n kiểu int	11/20	sai test 10, 11, 12, 13, 14, 15, 16, 18, 19
Tăng keo += 3 trước rồi mới cộng (em đầu nhận 4 viên)	1/20	sai test 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Dùng do … while (luôn chạy ít nhất 1 lần)	19/20	sai test 3

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.007s	Full điểm
	Python	20/20	0.037s	Full điểm
Tổng int	C++	15/20	–	Mất 5 test
Công thức với int	C++	11/20	–	Mất 9 test
Sai thứ tự	C++	1/20	–	Mất 19 test
do-while	C++	19/20	–	Mất 1 test

Ghi chú của mình: thứ tự hai câu lệnh trong thân vòng lặp rất quan trọng: phát trước, tăng sau. Và luôn thử trường hợp vòng lặp không chạy lần nào ($N = 0$).

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 😇