USACO 2026 - Purchasing Milk
Xem PDFNhân Ngày Sữa Quốc gia, Farmer John đang đưa ra mức giá đặc biệt cho các xô sữa! Ông có \(N\) (\(1\leq N\leq 10^5\)) ưu đãi được đánh số từ \(1\) đến \(N\). Với ưu đãi thứ \(i\), ông bán \(2^{i-1}\) xô sữa với giá \(a_i\) (\(1\leq a_i\leq 10^9\), \(a_i<a_{i+1}\)) mooney. Có thể sử dụng cùng một ưu đãi với số lần là bất kỳ số nguyên không âm nào.
Bạn đang cân nhắc \(Q\) (\(1\leq Q\leq 10^4\)) truy vấn độc lập. Với mỗi truy vấn, bạn nghĩ đến một số nguyên \(x\) (\(1\leq x\leq 10^9\)) và muốn biết chi phí nhỏ nhất để mua ít nhất \(x\) xô sữa.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\).
Dòng tiếp theo chứa \(a_1,a_2,\ldots,a_N\).
Mỗi dòng trong \(Q\) dòng tiếp theo chứa một số nguyên \(x\), biểu diễn một truy vấn.
Dữ liệu ra
Với mỗi truy vấn, in chi phí nhỏ nhất trên một dòng mới.
Lưu ý rằng các số nguyên có giá trị lớn trong bài toán này có thể yêu cầu sử dụng kiểu số nguyên 64 bit (ví dụ: long long trong C/C++).
Ví dụ
Ví dụ 1
Input
2 4
10 15
1
2
6
7Output
10
15
45
55Note
Trong ví dụ trên, Farmer John đưa ra \(2\) ưu đãi: \(1\) xô sữa với giá \(10\) mooney và \(2\) xô sữa với giá \(15\) mooney.
Chi phí thấp nhất để mua \(1\) xô chính là giá của ưu đãi \(1\) xô, và chi phí thấp nhất để mua \(2\) xô chính là giá của ưu đãi \(2\) xô.
Để có \(6\) xô, cách rẻ nhất là mua ưu đãi \(2\) xô tổng cộng \(3\) lần, với tổng chi phí là \(45\) mooney.
Để có \(7\) xô, cách rẻ nhất là mua ưu đãi \(2\) xô tổng cộng \(3\) lần và ưu đãi \(1\) xô một lần, với tổng chi phí là \(55\) mooney.
Ví dụ 2
Input
4 10
10 25 30 70
1
2
3
4
5
6
7
8
15
101Output
10
20
30
30
40
50
60
60
120
760Note
Trong ví dụ này, Farmer John đưa ra tổng cộng \(4\) ưu đãi tương ứng với \(1\), \(2\), \(4\) và \(8\) xô. Với mỗi truy vấn trong \(10\) truy vấn, kết quả tương ứng cho biết chi phí nhỏ nhất để mua ít nhất lượng sữa đó. Đôi khi, mua nhiều hơn lượng được chỉ định lại rẻ hơn.
Phân nhóm
- Test 3–4: \(N\leq 2\).
- Test 5–8: \(N\leq 10\).
- Test 9–16: Không có thêm ràng buộc.
Nguồn
USACO 2026 Contest 2, Bronze Division — bài gốc Purchasing Milk, tác giả: Chongtian Ma.
https://usaco.org/index.php?page=viewproblem2&cpid=1565
Kỳ thi:
- USACO 2026 Second Contest, Bronze (7 Tháng ba, 2026)
Bình luận