Khuyến mãi bia

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp while Mô phỏng

Đề bài

Một cửa hàng có chương trình khuyến mãi: cứ đem 10 vỏ chai đến cửa hàng thì được đổi lấy 3 chai mới. Bờm mua $n$ chai. Uống hết thì Bờm đem vỏ đi đổi, chai mới uống xong lại có vỏ để đổi tiếp… Vỏ chai chưa đủ 10 thì được giữ lại để gom với vỏ của lần sau (cửa hàng không cho "mượn" vỏ).

Hỏi Bờm uống được nhiều nhất bao nhiêu chai?

Dữ liệu vào:

Một số nguyên dương $n$ là số chai mua ban đầu.

Kết quả:

In ra tổng số chai Bờm uống được nhiều nhất.

Giới hạn:

• $1 \le n \le 3000$

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

10

Ví dụ 1 – output

13

Ví dụ 2 – input

24

Ví dụ 2 – output

33

• Ví dụ 1: uống 10 chai, đổi 10 vỏ được 3 chai, uống tiếp. Còn 3 vỏ không đổi được nữa. Tổng $10 + 3 = 13$.
• Ví dụ 2: uống 24 chai → đổi 20 vỏ được 6 chai, còn dư 4 vỏ. Uống 6 chai → có $4 + 6 = 10$ vỏ, đổi được 3 chai. Uống 3 chai → còn 3 vỏ. Tổng $24 + 6 + 3 = 33$.

Nguồn: phỏng theo bài "KHUYẾN MÃI" – vinhdinhcoder.net (chủ đề Lặp WHILE).

Lời mở đầu

Đổi vỏ lấy chai mới, chai mới lại cho vỏ để đổi tiếp… Không có công thức gọn, nên ta mô phỏng đúng như ngoài đời bằng while. Chỗ hay sai: quên giữ lại vỏ dư của lượt trước. Ghi chú: đề gốc không nói vỏ dư xử lý thế nào và có được "mượn" vỏ không; mình ghi rõ: vỏ dư được giữ lại, không được mượn.

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ưởngmô phỏng đổi vỏ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. Mọi test thoả $1 \le n \le 3000$.

Test	Nội dung kiểm tra
1–2	Ví dụ đề: đúng 10 vỏ, và 24 (vỏ dư 4 phải gom với vỏ mới)
3–6	Chưa đủ 10 vỏ ($n = 1, 9$), đổi 1 lượt ($13$), $20$
7–10, 19–20	Số nhỏ cần nhiều lượt đổi, vỏ dư góp lại thành 10
11–18	$n$ lớn tới $3000$: 6–7 lượt đổi

Ý tưởngMô phỏng: còn ≥ 10 vỏ thì còn đổi

Dùng hai biến: tong – số chai đã uống, vo – số vỏ đang có. Ban đầu uống hết $n$ chai: tong = vo = n.

Chừng nào vo >= 10:

• đem đổi được vo / 10 phần, mỗi phần 3 chai → moi = vo / 10 * 3 chai mới;
• uống hết: tong += moi;
• số vỏ bây giờ = vỏ dư chưa đổi (vo % 10) + vỏ của chai mới (moi).

Vì sao không có công thức n · 13 / 10?

Chai mới lại sinh vỏ mới, vỏ dư của lượt này góp sang lượt sau – con số cuối cùng phụ thuộc vào từng lượt đổi. Với $n = 24$: $24 \cdot 13 / 10 = 31$, nhưng đáp án là $33$.

Mỗi lượt đổi, số vỏ giảm ít nhất 7 (đem 10 đi, nhận về 3) và thực ra giảm còn khoảng 30%, nên vòng lặp chỉ chạy vài lần.

Em nhập số chai mua ban đầu rồi bấm Tiếp để xem từng lượt đổi vỏ:

n =

Ví dụ nhanh:

Lời giảiwhile (vo >= 10)

$n \le 3000$ nên dùng int là đủ.

C++▶ Chạy tay từng dòng codeCòn đủ 10 vỏ thì đổi, uống chai mới, cập nhật số vỏ.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Thứ tự trong vòng lặp quan trọng: phải tính vo % 10 từ số vỏ cũ, nên cập nhật vo ở câu cuối cùng.
2. vo / 10 * 3: chia nguyên trước rồi mới nhân. Viết vo * 3 / 10 sẽ sai (ví dụ $vo = 24$: $72 / 10 = 7$ chai, nhưng thật ra chỉ đổi được $6$).

Không gian$O(1)$

Thời gian$O(\log n)$ – vài vòng lặp

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.008s. Bản Python đúng 20/20 test, chạy lâu nhất 0.045s. 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ú
Bỏ vỏ dư: vo = moi	7/20	sai test 2, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20
Chỉ đổi 1 lượt: n + n / 10 * 3	5/20	sai test 2, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Công thức n * 13 / 10	4/20	sai test 2, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Điều kiện lặp vo > 10	17/20	sai test 1, 2, 12

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.008s	Full điểm
	Python	20/20	0.045s	Full điểm
Bỏ vỏ dư	C++	7/20	–	Mất 13 test
Đổi 1 lượt	C++	5/20	–	Mất 15 test
n*13/10	C++	4/20	–	Mất 16 test
vo > 10	C++	17/20	–	Mất 3 test

Ghi chú của mình: khi một quá trình "sinh ra" thứ dùng được cho bước sau (vỏ → chai → vỏ), đừng vội tìm công thức – mô phỏng bằng while vừa đúng vừa dễ kiểm tra.

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 😇