Mua quà

Nguồn: CLUE OJ Độ khó: Dễ Rẽ nhánh Tham lam

Đề bài

Tony vừa giành chức vô địch một cuộc thi lập trình và muốn mua kẹo về tặng các bạn trong lớp. Tony cần mua đúng $x$ cái kẹo loại 1 và $y$ cái kẹo loại 2. Kẹo loại 1 giá $u$ đồng một cái, kẹo loại 2 giá $v$ đồng một cái.

Bà chủ quán cũng mê lập trình nên tặng Tony thêm một ưu đãi: sau khi mua, Tony được đổi một cái kẹo loại này lấy một cái kẹo loại kia, mỗi lần đổi một cái kẹo mất phí $t$ đồng (Tony được đổi bao nhiêu cái tuỳ ý).

Hãy tính số tiền ít nhất Tony phải trả để cuối cùng có đúng $x$ cái kẹo loại 1 và $y$ cái kẹo loại 2.

Dữ liệu vào:

Một dòng gồm 5 số nguyên dương $x, y, u, v, t$.

Kết quả:

In ra một số nguyên là số tiền ít nhất Tony phải trả.

Giới hạn:

• $1 \le x, y, u, v, t \le 10^9$

Subtask:

• Subtask 1 (40% số điểm): $x, y, u, v, t < 320$.
• Subtask 2 (60% 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

2 2 500 1000 500

Ví dụ 1 – output

3000

Ví dụ 2 – input

3 5 500 600 100

Ví dụ 2 – output

4500

Ví dụ 3 – input

5 7 300 10 100

Ví dụ 3 – output

620

• Ví dụ 1: mua thẳng 2 kẹo loại 1 hết $2 \cdot 500 = 1000$ đồng và 2 kẹo loại 2 hết $2 \cdot 1000 = 2000$ đồng, tổng $3000$ đồng. (Mua loại 1 rồi đổi sang loại 2 cũng tốn $500 + 500 = 1000$ đồng một cái, không rẻ hơn.)
• Ví dụ 2: mua thẳng 3 kẹo loại 1 hết $1500$ đồng và 5 kẹo loại 2 hết $3000$ đồng, tổng $4500$ đồng.
• Ví dụ 3: kẹo loại 1 giá $300$ đồng, nhưng mua kẹo loại 2 (giá $10$ đồng) rồi đổi sang loại 1 chỉ tốn $10 + 100 = 110$ đồng một cái. Vậy Tony mua cả $5 + 7 = 12$ kẹo loại 2 rồi đổi 5 cái sang loại 1: $12 \cdot 10 + 5 \cdot 100 = 620$ đồng.

Nguồn: phỏng theo bài "Mua quà" – vinhdinhcoder.net (chủ đề Rẽ nhánh).

Lời mở đầu

Nghe thì có vẻ phải thử "đổi bao nhiêu cái", nhưng thật ra mỗi cái kẹo là một quyết định độc lập: cái kẹo loại 1 này mua thẳng, hay mua loại 2 rồi đổi? Chỉ cần so sánh hai cái giá là xong. Lưu ý: đề gốc cho nhiều trường hợp trong một test (cần vòng lặp – chưa học ở chương này), mình chuyển thành mỗi test một trường hợp, giữ nguyên nội dung bài toá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ưởnggiá rẻ nhất 1 cáiLờ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–8 thuộc subtask 1 (mọi số $< 320$), test 9–20 có số tới $10^9$, đáp án tới $2 \cdot 10^{18}$.

Test	Nội dung kiểm tra
1–8	Số nhỏ: không đổi, đổi loại 2 → loại 1, đổi loại 1 → loại 2, giá đổi bằng giá mua thẳng
9–11	Số tới $10^9$: tổng tiền tới $2 \cdot 10^{18}$ – tràn int
12–20	Sát nút: $v + t$ nhỏ hơn $u$ đúng 1 đồng, $u + t = v$, đổi theo cả hai chiều, số ngẫu nhiên lớn

Ý tưởngGiá rẻ nhất của từng loại kẹo

Muốn có 1 kẹo loại 1, Tony có hai cách: mua thẳng hết $u$ đồng, hoặc mua 1 kẹo loại 2 ($v$ đồng) rồi đổi ($t$ đồng) – tổng $v + t$. Vậy giá rẻ nhất cho 1 kẹo loại 1 là $g_1 = \min(u,\ v + t)$.

Tương tự, giá rẻ nhất cho 1 kẹo loại 2 là $g_2 = \min(v,\ u + t)$.

Vì mỗi cái kẹo chọn cách riêng, không ảnh hưởng nhau, đáp án là $x \cdot g_1 + y \cdot g_2$.

Chọn kiểu dữ liệu

$x \cdot g_1$ có thể tới $10^9 \cdot 10^9 = 10^{18}$, tổng tới $2 \cdot 10^{18}$ → dùng long long cho mọi biến (kể cả $u, v, t$, để $v + t$ và các phép nhân đều tính trong long long).

Em nhập dữ liệu rồi bấm Tiếp để xem chương trình xét từng điều kiện:

x = y = u = v = t =

Ví dụ nhanh:

Lời giảiHai lần so sánh, một phép tính

Mình không dùng hàm min mà viết bằng if cho đúng tinh thần chương rẽ nhánh: giả sử giá mua thẳng là rẻ nhất, gặp cách rẻ hơn thì cập nhật.

C++▶ Chạy tay từng dòng codeTính giá rẻ nhất của từng loại kẹo rồi nhân với số lượng.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Khai báo cả 5 biến là long long: nếu $u, v, t$ là int thì x * g1 vẫn đúng (vì x là long long), nhưng rất dễ quên – cứ đồng bộ long long cho an toàn.
2. Không cần xét "đổi bao nhiêu cái": nếu đổi một cái có lợi thì đổi tất cả cái cùng loại đều có lợi y như nhau.

Không gian$O(1)$

Thời gian$O(1)$

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.021s. 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ú
Dùng int cho mọi biến	9/20	sai test 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20
Chỉ xét đổi một chiều (mua loại 1 rồi đổi sang loại 2)	14/20	sai test 3, 6, 10, 12, 14, 19
Quên phí đổi $t$ (lấy giá rẻ hơn trong $u, v$ cho cả hai loại)	4/20	sai test 1, 2, 3, 4, 6, 8, 10, 11, 12, 13, 14, 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.003s	Full điểm
	Python	20/20	0.021s	Full điểm
Dùng int	C++	9/20	–	Mất 11 test
Chỉ đổi một chiều	C++	14/20	–	Mất 6 test
Quên phí đổi	C++	4/20	–	Mất 16 test

Ghi chú của mình: bài này không cần vòng lặp: phát hiện ra mỗi cái kẹo là một lựa chọn độc lập giúp lời giải chỉ còn 2 câu lệnh if.

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 😇