Purchasing Milk

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bác John bán $N$ gói sữa. Gói thứ $i$ cung cấp $2^{i - 1}$ xô sữa với giá $a_{i}$ đồng. Mỗi gói có thể mua nhiều lần.

Cho $Q$ truy vấn, mỗi truy vấn cho một số nguyên $x$ , hãy tìm chi phí tối thiểu để mua ít nhất $x$ xô sữa.

Dòng đầu tiên chứa hai số nguyên $N$ ( $1 \leq N \leq 10^{5}$ ) và $Q$ ( $1 \leq Q \leq 10^{4}$ ).
Dòng thứ hai chứa $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ ( $1 \leq a_{i} \leq 10^{9}$ , $a_{i} < a_{i + 1}$ ).
$Q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $x$ ( $1 \leq x \leq 10^{9}$ ).

Với mỗi truy vấn, in ra chi phí tối thiểu trên một dòng.

Input	Output	Giải thích
2 4 10 15 1 2 6 7	10 15 45 55	Gói 1: 1 xô giá 10. Gói 2: 2 xô giá 15. Mua 6 xô: 3 gói loại 2 = 45. Mua 7 xô: 3 gói loại 2 + 1 gói loại 1 = 55.
4 10 10 25 30 70 1 2 3 4 5 6 7 8 15 101	10 20 30 30 40 50 60 60 120 760	Ví dụ: mua 3 xô = 1 gói loại 2 (2 xô) giá 25 < 30 (gói 1 x 3), nhưng gói loại 3 cho 4 xô giá 30 rẻ hơn.

Bình luận

Không có bình luận tại thời điểm này.