Purchasing Milk
골드 IV의견: 0
On National Milk Day, Farmer John is offering exclusive prices on buckets of
milk! He has \(N\) (\(1 \leq N \leq 10^5\)) deals numbered from \(1\) to \(N\). For the
\(i\)'th deal, he is offering \(2^{i-1}\) buckets of milk for \(a_i\)
(\(1 \leq a_i \leq 10^9, a_i < a_{i+1}\)) moonies. The same deal may be taken any
non-negative integer number of times.
You are thinking about \(Q\) (\(1 \leq Q \leq 10^4\)) independent queries. For each query, you
have an integer \(x\) (\(1 \leq x \leq 10^9\)) in mind and wonder what is the
minimum cost to purchase at least \(x\) buckets of milk.
Problem credits: Chongtian Ma
SCORING
- Inputs 3-4: \(N \leq 2\)
- Inputs 5-8: \(N \leq 10\)
- Inputs 9-16: No additional constraints.
Problem credits: Chongtian Ma
The first line contains two integers \(N\) and \(Q\).
The following line contains \(a_1, a_2, \ldots, a_N\).
Each of the following \(Q\) lines contains an integer \(x\), representing a query.
For each query, output the minimum cost on a new line.
Note that the large size of integers involved in this problem may require the
use of 64-bit integer data types (e.g., a "long long" in C/C++).
2 4
10 15
1
2
6
710
15
45
55In the example above, Farmer John is offering 2 deals: 1 bucket of milk for 10
moonies and 2 buckets of milk for 15 moonies.
The cheapest cost to buy 1 bucket is just the cost of the 1 bucket deal and the
cheapest cost to buy 2 buckets is just the cost of the 2 bucket deal.
To get 6 buckets, the cheapest way is to purchase 3 of the 2 bucket deal for a
total of 45 moonies.
To get 7 buckets, the cheapest way is to purchase 3 of the 2 bucket deal and 1
of the 1 bucket deal for a total of 55 moonies.
4 10
10 25 30 70
1
2
3
4
5
6
7
8
15
10110
20
30
30
40
50
60
60
120
760In this example, Farmer John is offering a total of 4 deals for 1, 2, 4, and 8
buckets. For each of the 10 queries, the corresponding output indicates the
minimum cost to purchase at least that amount of milk. Sometimes, it is cheaper
to purchase more than the specified amount.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Bronze
평가 및 의견
Purchasing Milk
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Purchasing Milk