Cocacola
Đề bài
Cửa hàng cạnh nhà Hà đang có khuyến mãi như sau: nếu có $K$ vỏ chai cocacola thì người ta sẽ đổi cho một chai mới. Hiện tại Hà có $N$ chai còn nguyên, em quyết định mời hết bạn bè đến nhà để uống bằng hết và tận dụng khuyến mãi của cửa hàng để đổi mới và uống được càng nhiều càng tốt.
Yêu cầu: tính xem Hà và các bạn có thể uống được tối đa bao nhiêu chai cocacola.
Dữ liệu: gồm một dòng chứa hai số nguyên dương $N$ và $K$ $(N \le 10^9,\ 2 \le K \le 10^9)$.
Kết quả: gồm một số là kết quả tìm được.
9 313Giải thích ví dụ: ban đầu có 9 chai, uống hết sẽ có 9 cái vỏ, lại đổi được 3 chai mới; uống hết 3 chai mới sẽ có 3 vỏ, lại đổi được 1 chai nữa. Vậy tổng là $9 + 3 + 1 = 13$.
Lời mở đầu
Bài "đổi vỏ lấy chai" là bài khởi động rất quen thuộc của phần Tham lam: cứ có đủ $K$ vỏ là đổi ngay, không có lý do gì để chờ. Cái khó (nhỏ thôi) nằm ở chỗ $N$ tới $10^9$, nên mình sẽ đi qua 3 cách: mô phỏng đổi từng chai, mô phỏng đổi cả lô và cuối cùng là một công thức $O(1)$ – mỗi cách đều chạy thật trên bộ test của CLUE.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | N | K | Đáp án | Số lần đổi (≈ số vòng lặp của Cách 1) |
|---|---|---|---|---|
| 1 – 30 | 1 … 49 | 2 … 10 | 1 … 65 | 0 … 32 |
| 31 – 95 | 1.231.821 … 982.668.594 | 2 … 994 | 1.233.616 … 1.219.371.139 | 1.795 … 609.685.569 |
| 96 – 100 | 1.000.000.000 | 4 … 10 | 1.111.111.111 … 1.333.333.333 | 111.111.111 … 333.333.333 |
- Bộ test có 100 test. Đề không chia subtask, nhưng bộ test chia rõ 2 nhóm: test 1–30 rất nhỏ ($N \le 49$, $K \le 10$), test 31–100 có $N$ tới $10^9$ (5 test cuối $N = 10^9$ đúng bằng giới hạn).
- Có 6 test với $K = 2$ (test 10, 13, 16, 20, 68, 71) – trường hợp số lần đổi nhiều nhất. Có các test $N < K$ (test 2, 18, 24–25): không đổi được chai nào, đáp án chính là $N$.
- Đáp án lớn nhất trong bộ test là 1.333.333.333. Về lý thuyết đáp án có thể tới gần $2 \cdot 10^9$ (khi $N = 10^9$, $K = 2$), rất sát giới hạn của
int($\approx 2{,}147 \cdot 10^9$), chỉ cần cộng thêm chút là tràn số – cứ dùnglong longcho chắc.
Kết quả chạy thật của các cách trên từng nhóm test:
| Nhóm | Điều kiện | Các test | Cách 1 C++ | Cách 1 Python | Cách 2 C++ / Python | Cách 3 C++ / Python |
|---|---|---|---|---|---|---|
| Nhỏ | $N \le 49$ | 1 – 30 | 30/30 | 30/30 | 30/30 | 30/30 |
| Lớn | $N \le 10^9$ | 31 – 100 | 70/70 | 35/70 | 70/70 | 70/70 |
Ý tưởngCó đủ K vỏ là đổi ngay
Ta theo dõi 2 con số: uong – số chai đã uống, và vo – số vỏ đang cầm trong tay.
- Ban đầu uống hết $N$ chai:
uong = N,vo = N. - Chừng nào còn
vo >= Kthì mang $K$ vỏ đi đổi lấy 1 chai, uống luôn chai đó (uongtăng 1) và lại có thêm 1 vỏ.
Vì sao tham lam đúng? Mỗi lần đổi chỉ làm lợi (thêm 1 chai uống) và số vỏ không bao giờ "hết hạn", nên đổi sớm hay đổi muộn cũng như nhau – miễn là không bỏ phí lần đổi nào. Quá trình chỉ dừng khi số vỏ còn lại $< K$, lúc đó chắc chắn không thể đổi thêm.
Em nhập $N$, $K$ rồi bấm Tiếp để xem từng lượt uống – đổi (chai đỏ là chai còn nguyên, ô xám là vỏ; các vỏ cùng màu viền được gom thành một nhóm $K$ vỏ để đổi):
Cách 1Đổi từng chai một
Cài đặt đúng như lời kể: mỗi vòng lặp đổi đúng một chai.
- Mỗi vòng lặp:
vo -= k(đưa $K$ vỏ cho cửa hàng),uong++(uống chai mới),vo++(chai vừa uống thành vỏ). Tức là mỗi lần đổi, số vỏ giảm đúng $K - 1$. - Số vòng lặp bằng số lần đổi, khoảng $\dfrac{N}{K - 1}$. Với $K = 2$ và $N = 10^9$ là gần $10^9$ vòng lặp!
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.218s; bản Python đúng 65/100 test (quá thời gian ở test 31, 41, 45, 48, 51–53, 59, 67–68, 70–72, 76, 78–79, 81, 83–100), test đúng chạy lâu nhất 0.573s.
Bản C++ qua hết là vì vòng lặp cực kỳ đơn giản (3 phép tính, trình biên dịch tối ưu rất tốt) và bộ test lớn nhất chỉ cần khoảng $6{,}1 \cdot 10^8$ lần đổi. Bản Python thì không có may mắn đó: các test có $K$ nhỏ đều quá thời gian. Ta cần cách đổi nhanh hơn.
Cách 2Đổi cả lô một lần
Thay vì đổi từng chai, mỗi lượt ta mang tất cả vỏ đi đổi: với vo vỏ thì đổi được moi = vo / k chai mới, còn dư vo % k vỏ lẻ. Uống hết moi chai mới thì có thêm moi vỏ. Đây chính là cách đề bài giải thích ví dụ ($9 \to 3 \to 1$).
vo = vo % k + moi: vỏ lẻ còn dư cộng với vỏ của các chai vừa uống.- Sau mỗi lượt số vỏ còn khoảng $\dfrac{vo}{K} + K$, tức là giảm ít nhất một nửa (vì $K \ge 2$) cho đến khi xuống dưới $2K$. Nên số lượt chỉ khoảng $\log_2 N \approx 30$.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.006s; bản Python đúng 100/100 test, test đúng chạy lâu nhất 0.035s.
Cách 3Một công thức O(1)
Nhìn lại Cách 1: mỗi lần đổi, số vỏ giảm đúng $K - 1$. Được đổi khi còn ít nhất $K$ vỏ, tức là sau khi đổi vẫn còn ít nhất 1 vỏ. Vậy: bắt đầu với $N$ vỏ, đổi $e$ lần được khi và chỉ khi
$N - e \cdot (K - 1)$ $\ge 1 \iff e$ $\le \dfrac{N - 1}{K - 1}$
Kiểm tra với ví dụ: $9 + \lfloor 8 / 2 \rfloor$ $= 9 + 4$ $= 13$. Đúng! Cách nhìn dễ nhớ: giữ riêng 1 vỏ ra, $N - 1$ vỏ còn lại chia thành các nhóm $K - 1$ vỏ – mỗi nhóm cùng với "vỏ giữ riêng" đủ $K$ vỏ để đổi một chai, uống xong chai đó lại có lại đúng 1 vỏ để giữ riêng.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.006s; bản Python đúng 100/100 test, test đúng chạy lâu nhất 0.033s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Đổi từng chai | C++ | 100/100 | 0.218s | Full điểm |
| Python | 65/100 | 0.573s | Quá thời gian ở test 31, 41, 45, 48, 51–53, 59, 67–68, 70–72, 76, 78–79, 81, 83–100 | |
| 2. Đổi cả lô | C++ | 100/100 | 0.006s | Full điểm |
| Python | 100/100 | 0.035s | Full điểm | |
| 3. Công thức | C++ | 100/100 | 0.006s | Full điểm |
| Python | 100/100 | 0.033s | Full điểm |
Nhận xét
Đăng nhận xét