Statistics

Problem Statement for "GoldMining"

Problem Statement

You just found a gold mine that contains goldInGround units of gold. Currently, you don't have any units of gold. You have miningTime minutes of time. Once that time elapses, you want to have as much gold as possible.

You can mine the gold yourself, at the rate of one unit of gold per minute. At the beginning of each minute, you can also hire as many additional workers as you wish. Each worker requires an immediate one-time payment of hiringCost gold. (You can only hire a worker if you have enough gold to pay them.) A hired worker mines gold at the same rate as you. All gold mined by the workers belongs to you.

Return the maximum amount of gold you can have after miningTime minutes.

Definition

Class:
GoldMining
Method:
maxProfit
Parameters:
long, long, long
Returns:
long
Method signature:
long maxProfit(long goldInGround, long miningTime, long hiringCost)
(be sure your method is public)

Constraints

  • goldInGround will be between 1 and 10^18, inclusive.
  • miningTime will be between 1 and 10^6, inclusive.
  • hiringCost will be between 1 and 10^18, inclusive.

Examples

  1. 470000

    1000000

    50

    Returns: 470000

    There are 470,000 units of gold in the ground and you have 1,000,000 minutes. In that time you can mine all the gold on your own, there is no need to waste some of it on hiring help.

  2. 470000

    100000

    1234567890123456

    Returns: 100000

    There are 470,000 units of gold in the ground and you only have 100,000 minutes to mine it. Sadly, workers are prohibitively expensive and thus your best bet is still to work on your own the whole time.

  3. 470000

    100000

    57000

    Returns: 100000

    This gets a bit more tricky: After 57,000 minutes you already have enough gold to hire an extra worker, but you should not do so. Regardless of when exactly you hire the worker, it will never pay off. You will earn more just by mining alone.

  4. 470000

    100000

    42000

    Returns: 116000

    As the workers become cheaper, it becomes a good idea to hire one and end with more than 100,000 units of gold.

  5. 567890

    4

    1

    Returns: 8

    One of multiple optimal strategies looks as follows: First minute: Only you mine. You gain 1 gold. Hire a worker, pay 1 gold. You now have 0 gold. Second minute: You mine together with 1 worker. You gain 2 gold. Hire two workers, pay 2 gold. You now have 0 gold again. Third minute: You mine together with 3 workers. You gain 4 gold. Hire one more worker, pay 1 gold. You now have 3 gold left. Fourth minute: You mine together with 4 workers. You gain 5 gold, so you end with 3+5 = 8 gold.

  6. 234567

    47

    10

    Returns: 215

    Here you will eventually hire a bunch of extra workers. Sometimes you will even hire two new workers at the same time.

  7. 300

    47

    10

    Returns: 190

    The mining time and the cost to hire the worker are the same as in the previous example, but now the total amount of gold in the ground is quite small. Note that this influences hiring decisions: it does not pay off to hire as many workers as in the previous example.

  8. 987654321098765432

    100

    3

    Returns: 2731288513472

    If the workers are really cheap, in mere 100 minutes we can mine an awful lot of gold.

  9. 151713147151608135

    292265

    20928

    Returns: 5019710120

  10. 800703588685892536

    24

    1519

    Returns: 24

  11. 372361468765144

    335653

    796

    Returns: 371433369197268

  12. 14006779376578

    155889

    371196

    Returns: 155889

  13. 893242112422040853

    502740

    1621

    Returns: 890077464475233433

  14. 417195945882738841

    878459

    85577

    Returns: 507559535

  15. 7

    1

    1

    Returns: 1

  16. 882352940377020921

    932034

    283693

    Returns: 1705608

  17. 52424973457907584

    719397

    64791

    Returns: 888482114

  18. 517106323717774815

    1

    666945

    Returns: 1

  19. 37783148103732654

    446547

    672693

    Returns: 446547

  20. 794308468935233319

    939765

    21076

    Returns: 746337200347261183

  21. 733049010439060832

    930247

    4

    Returns: 733045857968659828

  22. 7137318

    900172

    154687

    Returns: 5281074

  23. 23910873029815

    52866

    1

    Returns: 23910420499654

  24. 595363686256173959

    3363

    949394

    Returns: 3363

  25. 9

    8

    7

    Returns: 8

  26. 1

    1

    29

    Returns: 1

  27. 10

    1

    2

    Returns: 1

  28. 73317

    24

    479436

    Returns: 24

  29. 24299896

    59

    261745

    Returns: 59

  30. 77310

    48562

    6

    Returns: 77304

  31. 32668455100594471

    598523

    308

    Returns: 32651430584719643

  32. 1

    690621

    24810

    Returns: 1

  33. 875903200042123277

    513022

    161007885428476854

    Returns: 513022

  34. 401576967683279578

    127712

    434810

    Returns: 127712

  35. 20015399

    31

    172

    Returns: 31

  36. 57210971239355263

    102

    129865

    Returns: 102

  37. 674564836640031413

    2

    96

    Returns: 2

  38. 3

    8

    4

    Returns: 3

  39. 4

    1

    7

    Returns: 1

  40. 18859634632697196

    1322

    6

    Returns: 18759308906669088

  41. 15850277047606104

    1

    1

    Returns: 1

  42. 693409749551919235

    3259

    31240

    Returns: 3259

  43. 2772

    581148

    317469

    Returns: 2772

  44. 1

    232451

    11400

    Returns: 1

  45. 381346591079096429

    11085

    165

    Returns: 370668173650536284

  46. 2001952

    222150

    921689

    Returns: 222150

  47. 445823155279632758

    125955

    850947

    Returns: 125955

  48. 3430

    58207

    917414

    Returns: 3430

  49. 319653937293492634

    986755

    707911

    Returns: 986755

  50. 564942263512621033

    4405

    776

    Returns: 47112

  51. 96816400434

    829213

    81

    Returns: 96806932668

  52. 26841735911425581

    117

    315619

    Returns: 117

  53. 1

    116202

    1

    Returns: 1

  54. 10

    6

    9

    Returns: 6

  55. 134968361615629733

    947174

    752803169336389869

    Returns: 947174

  56. 562319

    227116

    3

    Returns: 562313

  57. 10

    2

    10

    Returns: 2

  58. 6

    1

    10

    Returns: 1

  59. 766131598630813559

    103

    3673

    Returns: 103

  60. 1

    5

    1

    Returns: 1

  61. 286797543104729

    362

    20665

    Returns: 362

  62. 5138645452725880

    160

    641879

    Returns: 160

  63. 419376399054523446

    566126

    886019

    Returns: 566126

  64. 216179121847

    1204

    784406

    Returns: 1204

  65. 799478844945878586

    285694

    166013

    Returns: 285694

  66. 365056607413401509

    3

    782780

    Returns: 3

  67. 1285725530

    399195

    158344

    Returns: 485037

  68. 39820130506439976

    835134

    777725

    Returns: 835134

  69. 131358880112929382

    657885

    1

    Returns: 131358680433360676

  70. 447153714036928926

    1882

    846743

    Returns: 1882

  71. 1

    240070

    794457

    Returns: 1

  72. 937848312308021273

    12

    510914

    Returns: 12

  73. 250251361832144075

    207991

    28

    Returns: 250217545841410655

  74. 168033476619994187

    855706

    487727

    Returns: 855706

  75. 9

    2

    2

    Returns: 2

  76. 193843

    505542

    462650

    Returns: 193843

  77. 1437536

    60

    156928

    Returns: 60

  78. 690

    409081

    108

    Returns: 690

  79. 9

    3

    9

    Returns: 3

  80. 183925

    553699

    293879

    Returns: 183925

  81. 298711611470926225

    16240

    1

    Returns: 298693168962306353

  82. 407837520557692378

    950648

    650617663231695679

    Returns: 950648

  83. 35080051512

    597013

    912228

    Returns: 597013

  84. 96379162098709099

    717661

    227542

    Returns: 1218075

  85. 206722797104706524

    1

    374329

    Returns: 1

  86. 543621700182810

    24890

    1

    Returns: 543599829841211

  87. 1088942597

    617725

    1240

    Returns: 1086725477

  88. 412367812810

    559313

    14297

    Returns: 396265301868

  89. 10380821

    95497

    725746

    Returns: 95497

  90. 991846485005092162

    942753

    2691

    Returns: 988775661409047412

  91. 962303204669202200

    20897

    65357

    Returns: 20897

  92. 8541422642

    36

    582095

    Returns: 36

  93. 5

    9

    10

    Returns: 5

  94. 3

    3

    9

    Returns: 3

  95. 248012495892251467

    12

    721746

    Returns: 12

  96. 360184367354391

    649382

    65

    Returns: 360148242840056

  97. 28900557351908195

    8980

    700271

    Returns: 8980

  98. 9

    8

    10

    Returns: 8

  99. 15892825862931

    861897

    829344

    Returns: 861897

  100. 14318558

    1

    94494

    Returns: 1

  101. 1

    1

    368938

    Returns: 1

  102. 4183939

    31513

    3677

    Returns: 2827126

  103. 982449

    4293

    558380

    Returns: 4293

  104. 44775

    41

    539995

    Returns: 41

  105. 87793390

    22

    4556

    Returns: 22

  106. 8

    1

    2

    Returns: 1

  107. 5

    1

    9

    Returns: 1

  108. 462819247313323927

    17808

    501469

    Returns: 17808

  109. 2227667788062

    110712

    7761

    Returns: 2511360820

  110. 7

    2

    6

    Returns: 2

  111. 1

    580534

    1

    Returns: 1

  112. 650166809806686892

    547488

    901142026554305840

    Returns: 547488

  113. 1616702399157435

    2

    861505

    Returns: 2

  114. 634021667260990160

    249947

    504914

    Returns: 249947

  115. 4358

    827823

    559562

    Returns: 4358

  116. 8248521

    1

    599204

    Returns: 1

  117. 11

    4

    4831

    Returns: 4

  118. 633246294306777981

    671652

    27751

    Returns: 185901082691076

  119. 152

    887741

    4312

    Returns: 152

  120. 8

    4

    8

    Returns: 4

  121. 12550870652

    9

    35776

    Returns: 9

  122. 1777018925257142

    305592

    899

    Returns: 1771427015533240

  123. 27889692488

    12

    46363

    Returns: 12

  124. 775572732041986254

    474121

    558026

    Returns: 474121

  125. 27671438654171694

    21

    11918

    Returns: 21

  126. 8

    6

    1

    Returns: 7

  127. 367211915621266493

    8135

    109708

    Returns: 8135

  128. 17067506749

    822613

    994642

    Returns: 822613

  129. 139165043676058735

    101496

    705047

    Returns: 101496

  130. 559732720295214115

    1512

    289000

    Returns: 1512

  131. 9

    470

    3

    Returns: 9

  132. 900796855769723628

    5

    710

    Returns: 5

  133. 5

    10

    9

    Returns: 5

  134. 10

    4

    4

    Returns: 4

  135. 799

    391137

    154000

    Returns: 799

  136. 1015767586

    2552

    15

    Returns: 1009305031

  137. 570620991588247182

    654315

    258713

    Returns: 798736

  138. 949469610947879702

    439851

    518705

    Returns: 439851

  139. 6

    7

    3

    Returns: 6

  140. 575762043574601597

    53

    972518

    Returns: 53

  141. 180437

    46371

    320430

    Returns: 46371

  142. 7853509615965280

    718289

    437

    Returns: 7848664613445424

  143. 138204116568409549

    186

    556070

    Returns: 186

  144. 146070913512563227

    938127

    437311

    Returns: 1001632

  145. 3

    2

    3

    Returns: 2

  146. 203205637007492598

    20751

    39721

    Returns: 20751

  147. 801157111890674314

    637644

    892605

    Returns: 637644

  148. 3183908773

    424009

    640285

    Returns: 424009

  149. 855303281278447416

    58

    431964

    Returns: 58

  150. 8

    6

    9

    Returns: 6

  151. 340342398809655738

    33108

    9933

    Returns: 62564

  152. 32999

    68863

    17

    Returns: 32999

  153. 225230658969459474

    621459

    790674

    Returns: 621459

  154. 1

    128654

    56300

    Returns: 1

  155. 838295739760618386

    7

    486768

    Returns: 7

  156. 270675342008677857

    810917

    611113

    Returns: 810917

  157. 34339595178

    275399

    671467

    Returns: 275399

  158. 538837457874105051

    411442

    106266

    Returns: 1108186

  159. 1

    2

    7

    Returns: 1

  160. 393310512976406422

    647257

    426758

    Returns: 647257

  161. 38350906486876537

    1

    588195

    Returns: 1

  162. 1362

    18

    457

    Returns: 18

  163. 694790714671120744

    702046

    966552

    Returns: 702046

  164. 579221452012512576

    119673

    6

    Returns: 579192366584842410

  165. 195207187212478802

    952440

    12

    Returns: 195204726929105882

  166. 331613672399610811

    821817

    738991

    Returns: 821817

  167. 27875266358430065

    393708

    638166

    Returns: 393708

  168. 65112678585743810

    93141

    371828

    Returns: 93141

  169. 123860762835112090

    901989

    53873

    Returns: 207815408495

  170. 48274515

    22220

    50

    Returns: 48164065

  171. 556495650696534001

    13

    611146

    Returns: 13

  172. 33657517888457723

    23

    56144

    Returns: 23

  173. 523157046148692058

    863676

    501039997086049038

    Returns: 863676

  174. 184459664231695136

    784

    988889

    Returns: 784

  175. 740241567076283183

    1900

    418246

    Returns: 1900

  176. 487257357237951142

    237379

    61316

    Returns: 639176

  177. 11773869

    7

    488772

    Returns: 7

  178. 14623579298523999

    145294

    95

    Returns: 14613858468412734

  179. 642797673379990706

    8

    16090

    Returns: 8

  180. 5832731551445822

    78731

    5

    Returns: 5832360495173737

  181. 254020334249692975

    11853

    854970

    Returns: 11853

  182. 201322319550809672

    640040

    369712

    Returns: 640040

  183. 719936497077489919

    145847

    779351

    Returns: 145847

  184. 178748128324283041

    17327

    78

    Returns: 177818460333186937

  185. 1533858220

    3

    830213

    Returns: 3

  186. 772316261776456824

    769906

    137258

    Returns: 7806108

  187. 2981937

    385359

    895745

    Returns: 385359

  188. 372550565762212352

    589458

    204083

    Returns: 861222

  189. 10

    5

    10

    Returns: 5

  190. 17455

    819574

    381

    Returns: 17455

  191. 6489961925

    429136

    35488

    Returns: 1308367064

  192. 33354437553250

    284148

    841473

    Returns: 284148

  193. 857120430601131396

    112245

    802639

    Returns: 112245

  194. 120206877029944925

    129166

    355083

    Returns: 129166

  195. 709693886506030576

    1

    1

    Returns: 1

  196. 2

    1

    2

    Returns: 1

  197. 920370433586588

    906812

    3

    Returns: 920367388494911

  198. 1

    1

    1

    Returns: 1

  199. 663058584590709191

    1

    896

    Returns: 1

  200. 3533

    241414

    968445

    Returns: 3533

  201. 288191650397020198

    4384

    19

    Returns: 286739052218007394

  202. 156188231877019055

    6770

    14

    Returns: 155842762201028665

  203. 858471555

    466874

    980466

    Returns: 466874

  204. 5

    4

    10

    Returns: 4

  205. 645857068953247253

    408015

    1

    Returns: 645855485874742422

  206. 760361187826642914

    112874

    1

    Returns: 760354448965942100

  207. 87440612512604469

    651515

    110364

    Returns: 8404133

  208. 103878468869364701

    5

    850455

    Returns: 5

  209. 1794038752362887

    6228

    119734

    Returns: 6228

  210. 571235547515202529

    314278

    831858

    Returns: 314278

  211. 105112

    1351

    348

    Returns: 3663

  212. 70

    10777

    10

    Returns: 70

  213. 114964822086149433

    584990

    3

    Returns: 114964232423470104

  214. 7

    2

    5

    Returns: 2

  215. 987654321098765432

    1001

    3

    Returns: 984295874302122458

  216. 28

    6

    1

    Returns: 22

  217. 987654321098765432

    100

    1

    Returns: 966507087230325400

  218. 987654321098765400

    100000

    3

    Returns: 987624661120839018

  219. 519720749018566089

    493095

    98

    Returns: 519616891746934731

  220. 9

    4

    1

    Returns: 7

  221. 1000000000000000000

    1000000

    1

    Returns: 999998999961097956

  222. 1000000000

    66

    1

    Returns: 976428157

  223. 637342280896368832

    2404

    61

    Returns: 480793436705677049

  224. 134208905031

    1066

    42

    Returns: 109299121069

  225. 1000000000000000000

    1000000

    20000

    Returns: 954480683876916680

  226. 1574803

    711

    9

    Returns: 1552708

  227. 23310457

    32752

    307

    Returns: 23078672

  228. 83

    11

    1

    Returns: 74

  229. 999999999999999999

    1000000

    12345

    Returns: 981265704052655169

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: