Statistics

Problem Statement for "CardCosts"

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

  1. 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.

  2. 400

    1000

    Returns: 160000

    k is too large to be worthwhile. Purchase all cards on the first round.

  3. 1000000

    1000

    Returns: 999000001000

    Watch for overflow.

  4. 113772

    188

    Returns: 12875219937

  5. 350602

    706

    Returns: 122747696757

  6. 330669

    942

    Returns: 109226036466

  7. 367236

    137

    Returns: 133877938922

  8. 962674

    294

    Returns: 923589086442

  9. 587553

    929

    Returns: 344847014337

  10. 511197

    63

    Returns: 257174415253

  11. 66715

    693

    Returns: 4444477849

  12. 472060

    181

    Returns: 221609520776

  13. 913932

    679

    Returns: 834041553704

  14. 315555

    234

    Returns: 99149435518

  15. 600470

    301

    Returns: 359366360418

  16. 395774

    518

    Returns: 156334731966

  17. 819017

    27

    Returns: 645944984593

  18. 107857

    793

    Returns: 11618481169

  19. 490869

    246

    Returns: 239972910474

  20. 487757

    337

    Returns: 237200951117

  21. 159031

    535

    Returns: 25243643329

  22. 106365

    477

    Returns: 11289844897

  23. 928110

    190

    Returns: 856854681615

  24. 548299

    267

    Returns: 299505855493

  25. 316065

    803

    Returns: 99772834131

  26. 985423

    575

    Returns: 969369696881

  27. 868150

    127

    Returns: 747750267134

  28. 356076

    439

    Returns: 126501308268

  29. 150042

    442

    Returns: 22461679250

  30. 443282

    178

    Returns: 195395039856

  31. 784984

    226

    Returns: 613473389885

  32. 708657

    433

    Returns: 501034956561

  33. 528853

    900

    Returns: 279374832325

  34. 83447

    979

    Returns: 6956296319

  35. 987446

    86

    Returns: 963711972368

  36. 44131

    895

    Returns: 1945371619

  37. 471855

    865

    Returns: 222389848331

  38. 207236

    433

    Returns: 42847578110

  39. 660672

    247

    Returns: 434720367410

  40. 366493

    716

    Returns: 134129567653

  41. 191847

    152

    Returns: 36563143313

  42. 365176

    228

    Returns: 132768638392

  43. 42394

    14

    Returns: 1668879608

  44. 0

    654

    Returns: 0

  45. 123123

    1

    Returns: 123123

  46. 1000000

    1

    Returns: 1000000

  47. 1000000

    2

    Returns: 500000500000

  48. 986200

    73

    Returns: 959267415380

  49. 113772

    188

    Returns: 12875219937

  50. 1000000

    2

    Returns: 500000500000

  51. 3

    3

    Returns: 7

  52. 5986

    654

    Returns: 35777503

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: