CardCosts
SRM 245 · 2005-06-01 · by Enogipe
SRM 245 · 2005-06-01 · by Enogipe · Dynamic Programming, Greedy
Problem Statement
Problem Statement
You are a playing a card game consisting of 1 or more rounds in which you may purchase 1 or more cards during each round. The cost of buying c cards in round r is k^r * c^2 (in the first round, r = 0). For example, if k = 2, and you buy 4 cards in the first round, 1 card in the second round, and 1 card in the third round, it would cost:
- 2^0 * 4^2 = 16 for the first four cards,
- 2^1 * 1^2 = 2 for the fifth card,
- 2^2 * 1^2 = 4 for the last card.
Notes
- Watch for overflow errors; a 32-bit dataype is not sufficient for this problem.
Constraints
- n is between 0 and 1000000 inclusive.
- k is between 1 and 1000 inclusive.
Examples
0)
6 2 Returns: 21
This is the example from the problem definitiion. The best solution is to purchase 3 cards at 9, then 2 cards at 8, then 1 card at 4.
1)
400 1000 Returns: 160000
k is too large to be worthwhile. Purchase all cards on the first round.
2)
1000000 1000 Returns: 999000001000
Watch for overflow.
3)
113772 188 Returns: 12875219937
4)
350602 706 Returns: 122747696757
Submissions are judged against all 52 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CardCosts with a public method long long mincost(int n, int k) · 52 test cases · 2 s / 256 MB per case