TopCoder problem "CardCosts" used in SRM 245 (Division II Level Three)



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.
The six cards cost you 22. There is a cheaper way to buy 6 cards: buy 3, then 2, then 1 for a cost of 9+8+4 = 21. Suppose you wish to buy n cards given some round multipler k. Return the minimum cost of purchasing the cards.
 

Definition

    
Class:CardCosts
Method:mincost
Parameters:int, int
Returns:long
Method signature:long mincost(int n, int k)
(be sure your method is public)
    
 

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)
    
0
654
Returns: 0
5)
    
1000000
1
Returns: 1000000
6)
    
1000000
2
Returns: 500000500000

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4502

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7220&pm=4502

Writer:

Enogipe

Testers:

PabloGilberto , lbackstrom , brett1479 , vorthys

Problem categories:

Dynamic Programming, Greedy