Statistics

Problem Statement for "StrongEconomy"

Problem Statement

As a serious strategy-games player, you know how important it is for your country to have a strong economy. In order to make this happen, you've just built n factories and hired k specialists. Unfortunately, you now have no gold left, and you must figure out the fastest way to raise target units of gold.

In a single round, you earn F*S units of gold, where F is the number of factories and S is the number of specialists you currently have. At the end of each round, you can build more factories and hire more specialists. Building one new factory or hiring one new specialist costs price units of gold. As long as you can afford them, there is no limit to the number of factories and specialists you have. Return the minimum number of rounds required to earn at least target units of gold.

Definition

Class:
StrongEconomy
Method:
earn
Parameters:
long, long, long, long
Returns:
long
Method signature:
long earn(long n, long k, long price, long target)
(be sure your method is public)

Constraints

  • n, k, price and target will each be between 1 and 10^12, inclusive.

Examples

  1. 2

    1

    2

    10

    Returns: 4

    In the first round you will earn 2*1 = 2 units of gold and must spend them on hiring a new specialist. In each of the rounds that follow, you will earn 2*2 = 4 units of gold. You need 3 more rounds in order to earn at least 10 units of gold.

  2. 2

    1

    2

    9

    Returns: 3

    In the first round you will earn 2*1 = 2 units of gold and must spend them on hiring a new specialist. In the second round you will earn 2*2 = 4 units of gold and must spend them on building a factory and hiring another specialist. In the third round you will earn 3*3 = 9 units of gold.

  3. 1

    1

    500000

    1000002

    Returns: 1000001

    Wait 500000 rounds in order to earn 500000*1*1 = 500000 units of gold. At the end of the 500000th round, spend all your money to build a factory (or to hire a specialist). In each of the rounds that follow, you will earn 2*1 = 2 units of gold, so you need 500001 more rounds in order to earn the required 1000002 units of gold.

  4. 5

    4

    15

    100

    Returns: 5

    Don't spend your gold at all.

  5. 4294967296

    4294967296

    10

    10000

    Returns: 1

    4294967296*4294967296 = 0 in long long

  6. 4294967297

    4294967297

    1000000000000

    1000000000000

    Returns: 1

  7. 999999999999

    1844674408

    1000000000000

    1000000000000

    Returns: 1

  8. 1844674408

    999999999999

    1000000000000

    1000000000000

    Returns: 1

  9. 1

    1

    1000000000000

    1000000000000

    Returns: 1000000000000

  10. 1

    1

    499999999999

    1000000000000

    Returns: 999999999999

  11. 1000000000000

    1000000000000

    1000000000000

    1000000000000

    Returns: 1

  12. 1

    1

    1

    1

    Returns: 1

  13. 1

    100

    10000000000

    1000000000000

    Returns: 617737754

  14. 1

    1

    1

    1000000000000

    Returns: 8

  15. 1

    1

    2

    1000000000000

    Returns: 11

  16. 1

    1

    3

    1000000000000

    Returns: 14

  17. 1

    1

    4

    1000000000000

    Returns: 17

  18. 3

    2

    1000000000000

    222

    Returns: 37

  19. 3

    2

    1000000000000

    221

    Returns: 37

  20. 3

    2

    1000000000000

    223

    Returns: 38

  21. 3

    13

    10

    1000000000000

    Returns: 9

  22. 3

    13

    13

    1000000000000

    Returns: 10

  23. 3

    13

    15

    1000000000000

    Returns: 11

  24. 3

    13

    20

    1000000000000

    Returns: 12

  25. 3

    13

    28

    1000000000000

    Returns: 14

  26. 3

    13

    103

    1000000000000

    Returns: 36

  27. 3

    13

    104

    1000000000000

    Returns: 37

  28. 3

    13

    1006

    1000000000000

    Returns: 291

  29. 3

    13

    123124

    1000000000000

    Returns: 34513

  30. 3

    13

    1000000002

    1000000000000

    Returns: 279203910

  31. 3

    13

    1000000001

    1000000000000

    Returns: 279203909

  32. 1

    1000

    382

    943416963123

    Returns: 10

  33. 1000

    1

    383

    943416963123

    Returns: 11

  34. 1000000

    1000000

    1

    1000000000000

    Returns: 1

  35. 1000000

    999999

    1

    1000000000000

    Returns: 2

  36. 1000000

    499999

    999997

    1000000000000

    Returns: 3

  37. 499999

    1000000

    999996

    1000000000000

    Returns: 2

  38. 12

    12

    1

    143

    Returns: 1

  39. 1000

    1998

    1

    1000000000000

    Returns: 2

  40. 1997

    1000

    1

    1000000000000

    Returns: 3

  41. 987

    123

    368073595

    45654654654

    Returns: 376065

  42. 123

    987

    368073594

    45654654654

    Returns: 376064

  43. 84

    87

    92778

    1000000000000

    Returns: 2186

  44. 22

    63

    28

    1000000000000

    Returns: 7

  45. 84

    87

    92778

    145621303454

    Returns: 2185

  46. 35

    98

    29522

    502150818174

    Returns: 927

  47. 35

    98

    29522

    502150818173

    Returns: 926

  48. 91

    97

    3127

    771370491752

    Returns: 75

  49. 91

    97

    3127

    771370491751

    Returns: 74

  50. 28

    81

    64143

    93888052920

    Returns: 2449

  51. 28

    81

    64143

    93888052919

    Returns: 2448

  52. 30

    92

    52529

    86515142243

    Returns: 1801

  53. 30

    92

    52529

    86515142242

    Returns: 1800

  54. 79

    88

    83632

    211424343435

    Returns: 2019

  55. 79

    88

    83632

    211424343434

    Returns: 2018

  56. 1

    13

    56753

    105767073758

    Returns: 22463

  57. 1

    13

    56753

    105767073757

    Returns: 22462

  58. 76

    31

    8664

    45611934876

    Returns: 341

  59. 76

    31

    8664

    45611934875

    Returns: 340

  60. 80

    58

    16566

    342713655614

    Returns: 492

  61. 80

    58

    16566

    342713655613

    Returns: 491

  62. 7

    87

    28292

    93923261297

    Returns: 1504

  63. 7

    87

    28292

    93923261296

    Returns: 1503

  64. 84

    70

    59708

    227673130901

    Returns: 1566

  65. 84

    70

    59708

    227673130900

    Returns: 1565

  66. 9480

    3586

    4341516

    951594673810

    Returns: 1346

  67. 9480

    3586

    4341516

    951594673809

    Returns: 1345

  68. 6964

    3072

    8267111

    986932823619

    Returns: 3281

  69. 6964

    3072

    8267111

    986932823618

    Returns: 3280

  70. 3597

    7349

    9603447

    987954828389

    Returns: 3458

  71. 3597

    7349

    9603447

    987954828388

    Returns: 3457

  72. 4961

    6349

    7557037

    994257985210

    Returns: 2621

  73. 4961

    6349

    7557037

    994257985209

    Returns: 2620

  74. 4910

    2549

    480376

    818796097339

    Returns: 266

  75. 4910

    2549

    480376

    818796097338

    Returns: 265

  76. 3628

    2633

    3784890

    987247079590

    Returns: 2412

  77. 3628

    2633

    3784890

    987247079589

    Returns: 2411

  78. 5288

    777

    8231010

    992838524553

    Returns: 6036

  79. 5288

    777

    8231010

    992838524552

    Returns: 6035

  80. 5294

    7639

    9554422

    991960422948

    Returns: 2872

  81. 5294

    7639

    9554422

    991960422947

    Returns: 2871

  82. 1225

    2289

    7090455

    995869987239

    Returns: 8088

  83. 1225

    2289

    7090455

    995869987238

    Returns: 8087

  84. 5361

    3918

    8447708

    989936375521

    Returns: 3578

  85. 5361

    3918

    8447708

    989936375520

    Returns: 3577

  86. 10

    8

    3642580

    936880438446

    Returns: 833337

  87. 10

    8

    3642580

    936880438445

    Returns: 833336

  88. 3

    1

    7696204

    984177860500

    Returns: 9452948

  89. 3

    1

    7696204

    984177860499

    Returns: 9452947

  90. 1

    6

    3558508

    965326092682

    Returns: 2592533

  91. 1

    6

    3558508

    965326092681

    Returns: 2592532

  92. 1

    4

    2884010

    983805656183

    Returns: 2861393

  93. 1

    4

    2884010

    983805656182

    Returns: 2861392

  94. 1

    6

    7880343

    984495273963

    Returns: 5741134

  95. 1

    6

    7880343

    984495273962

    Returns: 5741133

  96. 3

    3

    580672

    438861324017

    Returns: 422897

  97. 3

    3

    580672

    438861324016

    Returns: 422896

  98. 8

    6

    8984325

    995480931503

    Returns: 2666724

  99. 8

    6

    8984325

    995480931502

    Returns: 2666723

  100. 5

    6

    5414971

    975522072980

    Returns: 2064834

  101. 5

    6

    5414971

    975522072979

    Returns: 2064833

  102. 3

    10

    1932826

    874055244560

    Returns: 653425

  103. 3

    10

    1932826

    874055244559

    Returns: 653424

  104. 2

    1

    3512032

    932346048017

    Returns: 5777060

  105. 2

    1

    3512032

    932346048016

    Returns: 5777059

  106. 6

    6

    50

    213602033266

    Returns: 25

  107. 6

    6

    50

    213602033265

    Returns: 24

  108. 1

    9

    58

    83533427519

    Returns: 39

  109. 1

    9

    58

    83533427518

    Returns: 38

  110. 1

    2

    4

    50527397092

    Returns: 13

  111. 1

    2

    4

    50527397091

    Returns: 12

  112. 5

    7

    34

    64976813964

    Returns: 19

  113. 5

    7

    34

    64976813963

    Returns: 18

  114. 9

    2

    75

    241740344

    Returns: 39

  115. 9

    2

    75

    241740343

    Returns: 38

  116. 6

    10

    82

    92738216440

    Returns: 29

  117. 6

    10

    82

    92738216439

    Returns: 28

  118. 10

    10

    16

    395711557

    Returns: 9

  119. 10

    10

    16

    395711556

    Returns: 8

  120. 6

    2

    8

    13880727677

    Returns: 11

  121. 6

    2

    8

    13880727676

    Returns: 10

  122. 7

    9

    70

    163852820

    Returns: 25

  123. 7

    9

    70

    163852819

    Returns: 24

  124. 7

    7

    67

    992061024

    Returns: 27

  125. 7

    7

    67

    992061023

    Returns: 26

  126. 1

    1

    2

    1

    Returns: 1

  127. 1

    1

    1

    2

    Returns: 2

  128. 1000000

    1

    440000000001

    1000000000000

    Returns: 940001

  129. 1000000

    2

    100010000012

    1000000000000

    Returns: 282915

  130. 987654321

    123

    5761316872

    1000000000000

    Returns: 8

  131. 123

    987654321

    5761316873

    1000000000000

    Returns: 9

  132. 10000

    10000

    15788

    1000000000000

    Returns: 8

  133. 10000

    10000

    15787

    1000000000000

    Returns: 7

  134. 6

    4

    3

    499

    Returns: 3

  135. 260

    1

    60

    1000

    Returns: 2

  136. 1

    17

    5

    65

    Returns: 2

  137. 1

    895

    9

    86775

    Returns: 2

  138. 1

    3734482

    9252

    1000000000

    Returns: 2

  139. 4674

    78

    2

    7011943259

    Returns: 2

  140. 15

    452

    5

    6472893737

    Returns: 3

  141. 3

    27838588957

    3828480610

    650785854029

    Returns: 2

  142. 1

    1

    1000000000000

    1000000000000

    Returns: 1000000000000

  143. 91

    7

    55

    8713

    Returns: 4

  144. 1

    74

    28

    10000

    Returns: 5

  145. 1

    2

    2248

    8327

    Returns: 2986

  146. 3297

    46

    668

    1000000000000

    Returns: 6

  147. 96334

    78197

    51308

    88893925229

    Returns: 3

  148. 248572

    2

    1

    1000000000000

    Returns: 3

  149. 4

    4

    3305161632

    172543446096

    Returns: 1700444920

  150. 55

    2

    8179801513

    888975049803

    Returns: 754944416

  151. 1

    1

    100000000000

    1000000000000

    Returns: 253976773118

  152. 1

    1

    10000000000

    1000000000000

    Returns: 26348839006

  153. 3

    2

    764

    7

    Returns: 2

  154. 1

    4

    27071

    5

    Returns: 2

  155. 1

    1

    82425

    7440

    Returns: 7440

  156. 1

    1

    6

    7

    Returns: 7

  157. 45

    51

    3

    1000000

    Returns: 3

  158. 5

    2

    96

    1000000

    Returns: 68

  159. 7

    5

    1000000

    837694

    Returns: 23935

  160. 1

    4

    8

    64994

    Returns: 12

  161. 5

    8

    17456

    1000000

    Returns: 5313

  162. 7

    2

    428

    294053

    Returns: 220

  163. 1

    3

    41370

    64590

    Returns: 21530

  164. 3

    1

    923

    7

    Returns: 3

  165. 2

    2

    2

    9

    Returns: 2

  166. 92

    1

    4

    93

    Returns: 2

  167. 3249

    1

    56231

    54412

    Returns: 17

  168. 2

    8

    228

    2179

    Returns: 80

  169. 12

    740

    1

    9079

    Returns: 2

  170. 7

    8

    7335

    1000000

    Returns: 1974

  171. 2

    6

    22577

    885642

    Returns: 12105

  172. 1

    1

    6

    45

    Returns: 16

  173. 943

    246

    938

    1000000

    Returns: 4

  174. 16

    1

    31558

    230365

    Returns: 6891

  175. 4

    4

    167732

    1000000

    Returns: 58870

  176. 6

    1

    274644

    1000000

    Returns: 124217

  177. 1

    1

    49

    756530

    Returns: 136

  178. 1

    1

    1

    1000000000000

    Returns: 8

  179. 1

    1

    10

    1000000000000

    Returns: 33

  180. 1

    1

    100

    1000000000000

    Returns: 273

  181. 1

    1

    1000

    1000000000000

    Returns: 2655

  182. 1

    1

    10000

    1000000000000

    Returns: 26461

  183. 1

    1

    100000

    1000000000000

    Returns: 264506

  184. 1

    1

    1000000

    1000000000000

    Returns: 2644946

  185. 1

    1

    10000000

    1000000000000

    Returns: 26449252

  186. 1

    1

    100000000

    1000000000000

    Returns: 264483415

  187. 1

    1

    1000000000

    1000000000000

    Returns: 2643933573

  188. 41337

    677

    6636

    383673609213

    Returns: 5

  189. 6

    743

    5450967460

    84582505642

    Returns: 14692623

  190. 758116

    106736

    59705004113

    668378083441

    Returns: 9

  191. 79938

    1

    1000000000000

    92986026562

    Returns: 1163227

  192. 542624

    8

    58516565619

    1000000000000

    Returns: 193371

  193. 4

    7393608740

    905752031

    973397687545

    Returns: 3

  194. 45

    389

    876475608

    2380906

    Returns: 137

  195. 39

    32089

    790

    2769032

    Returns: 2

  196. 7338

    1

    28946

    38580850

    Returns: 38

  197. 6

    85

    73043613

    4259253

    Returns: 8352

  198. 2012

    55

    967041998559

    67242205251

    Returns: 607647

  199. 239740

    1211

    258355746906

    26710515876

    Returns: 93

  200. 739

    8179

    9890869

    2486284511

    Returns: 412

  201. 3

    5

    95

    81733651

    Returns: 58

  202. 3

    4

    8654788

    721231

    Returns: 60103

  203. 2

    70075467

    93740664790

    3366257720

    Returns: 25

  204. 81

    38

    815

    6395792006

    Returns: 35

  205. 145

    64923

    83

    496943571

    Returns: 2

  206. 540

    212982169

    1

    1000000000000

    Returns: 2

  207. 93923041462

    4

    378647893704

    661454114213

    Returns: 2

  208. 9671769

    31

    850495

    10126386417

    Returns: 3

  209. 53859

    17

    13

    1000000000000

    Returns: 3

  210. 91

    861

    1000000000000

    5608419

    Returns: 72

  211. 73

    664

    290282596832

    6698079356

    Returns: 138185

  212. 83

    27330378

    95012370

    1000000000000

    Returns: 23

  213. 726

    1170

    774

    73026150

    Returns: 5

  214. 879749

    29

    295016

    227529435

    Returns: 3

  215. 5124

    898401

    12114610

    44944683511

    Returns: 10

  216. 4717089

    4240

    289671

    1000000000000

    Returns: 3

  217. 30888790

    4

    8

    1000000000000

    Returns: 2

  218. 43848

    32

    505917548846

    300193287281

    Returns: 213945

  219. 1

    8830402

    63729

    3336385497

    Returns: 3

  220. 588687

    5

    905752

    5050572958

    Returns: 16

  221. 5

    1882138

    669047

    1258441656

    Returns: 5

  222. 7707617

    92

    537132342567

    1000000000000

    Returns: 1411

  223. 9

    43

    562667616

    1496376

    Returns: 3867

  224. 7

    63404

    659

    58430401920

    Returns: 4

  225. 8476

    9328

    959

    84917635796

    Returns: 3

  226. 1604

    719

    3

    15722577518

    Returns: 2

  227. 2

    14

    997818496

    701950

    Returns: 25070

  228. 3525

    507

    147

    43488690

    Returns: 2

  229. 1

    42338

    27818450511

    80439574

    Returns: 1900

  230. 14240

    32208

    78

    74642634464

    Returns: 2

  231. 3200

    39

    9448744

    316770861

    Returns: 2539

  232. 9

    860808045

    2999253

    14375317480

    Returns: 2

  233. 8495

    5102047

    3145

    1000000000000

    Returns: 2

  234. 707

    8

    7

    42379447129

    Returns: 4

  235. 9115

    249268

    97762378

    186756434682

    Returns: 83

  236. 8

    6339899

    80920044046

    84387318

    Returns: 2

  237. 9045

    4526

    8

    4332054332

    Returns: 2

  238. 1

    5

    100

    1000000000000

    Returns: 92

  239. 4000000000

    4000000000

    1000000000000

    1000000000000

    Returns: 1

  240. 102143934434

    102143934434

    102333934434

    102143934434

    Returns: 1

  241. 1

    1

    66

    1000000000000

    Returns: 183

  242. 50

    1

    1000

    999999999999

    Returns: 139

  243. 105043115

    625352805

    9856896

    38371240

    Returns: 1

  244. 4294967297

    4294967297

    4294967297

    1000000000000

    Returns: 1

  245. 2

    1

    100000000

    1000000000000

    Returns: 164483415

  246. 3037000500

    3037000500

    3037000500

    3037000500

    Returns: 1

  247. 1000000000000

    12345678

    12213

    999999999999

    Returns: 1

  248. 1

    2

    1000000000

    1000000000000

    Returns: 1643933573

  249. 999999999999

    999999999999

    99999999

    999999999999

    Returns: 1

  250. 1

    1

    98978979781

    1000000000000

    Returns: 251485720935

  251. 100000

    100000

    1

    1000000000000

    Returns: 2

  252. 11000000000

    11000000000

    1

    1000000000000

    Returns: 1

  253. 4294967296

    4294967296

    1000000000000

    1000000000000

    Returns: 1

  254. 4294967296

    4294967296

    4294967296

    42949672960

    Returns: 1

  255. 1

    1

    10000001

    100000000002

    Returns: 26448352

  256. 20000000000

    20000000000

    1

    10000

    Returns: 1

  257. 2

    7

    23425258

    999999999999

    Returns: 11795137

  258. 1000000000000

    18446745

    1000000000000

    1000000000000

    Returns: 1

  259. 1

    199

    1000

    900000000000

    Returns: 49

  260. 1

    1

    220

    1000000000000

    Returns: 591

  261. 1000000000000

    1000000000000

    1000

    1000000000

    Returns: 1

  262. 90000000000

    900000000000

    123456789

    12345678912

    Returns: 1

  263. 4294967295

    4294967295

    100

    1000000000000

    Returns: 1

  264. 999998998117

    999998998117

    2323

    232323

    Returns: 1

  265. 1

    2

    1

    979789987999

    Returns: 7

  266. 10000000000

    1000000000

    5

    5

    Returns: 1

  267. 4294967296

    4294967296

    10000000000

    10000000000

    Returns: 1

  268. 38

    19

    191023

    1000000000000

    Returns: 13683

  269. 30000000000

    30000000000

    100000000000

    100000000000

    Returns: 1

  270. 10000000000

    950000000

    2

    1000000000000

    Returns: 1

  271. 3

    1

    5

    20000000000

    Returns: 12

  272. 999999994564

    123131312123

    999999999999

    123132131

    Returns: 1

  273. 9

    11

    100000

    100

    Returns: 2

  274. 1

    1

    400000000000

    1000000000000

    Returns: 850000000000

  275. 4000000000

    4000000000

    4000000000

    4000000000

    Returns: 1

  276. 123456789012

    215987654321

    50000000000

    1000000000000

    Returns: 1

  277. 20000000000

    20000000000

    1

    20000000000

    Returns: 1

  278. 4294967296

    4294967296

    1000000000

    10000000000

    Returns: 1

  279. 2

    1

    100000000000

    1000000000000

    Returns: 153976773118

  280. 5

    1

    2

    17

    Returns: 3

  281. 4294967296

    4294967296

    1

    1000000000000

    Returns: 1

  282. 3800000000

    1900000000

    191023

    1000000000000

    Returns: 1

  283. 10

    1

    234567

    1000000000000

    Returns: 114496

  284. 2

    3

    1000

    1000000000000

    Returns: 905

  285. 1000

    1000

    1

    1000000000000

    Returns: 3

  286. 4294967296

    4294967297

    1000000000

    10000000000

    Returns: 1

  287. 123858384657

    638592345063

    457893458243

    673840653456

    Returns: 1

  288. 18446744

    1000000000000

    1000000000000

    1000000000000

    Returns: 1

  289. 10000000000

    5000000000

    1123344554

    1000000000000

    Returns: 1

  290. 73014444049

    252645135

    10000000

    10000000

    Returns: 1

  291. 34359738368

    34359738368

    423

    535367567657

    Returns: 1

  292. 4294967295

    4294967296

    1

    1000000000000

    Returns: 1

  293. 10

    10

    101

    101

    Returns: 2

  294. 9999999999

    1

    1

    99999999999

    Returns: 2

  295. 4294967295

    1

    1

    10000000000

    Returns: 2

  296. 1

    1

    200

    1000000000000

    Returns: 538

  297. 4294967296

    4294967296

    4294967296

    4294967296

    Returns: 1

  298. 4294967296

    4294967296

    1000000000000

    2

    Returns: 1

  299. 1

    1

    1

    1000000000

    Returns: 8

  300. 2000

    2000

    1

    1000000000000

    Returns: 2

  301. 10

    1

    1000000000000

    12

    Returns: 2

  302. 4294967296

    4294967296

    10000000

    10000000

    Returns: 1

  303. 174094882455

    105957992

    234567

    1000000000000

    Returns: 1

  304. 1

    999

    10000

    25000

    Returns: 24

  305. 4294967296

    4294967296

    400000000000

    1000000000000

    Returns: 1

  306. 7

    1

    423

    9

    Returns: 2

  307. 4294967296

    4294967297

    1000000000000

    999999999999

    Returns: 1

  308. 1

    500

    26897

    99999999999

    Returns: 482

  309. 100

    1

    1

    1

    Returns: 1

  310. 10000000000

    1000000000

    100

    1000000000000

    Returns: 1

  311. 200000

    200000

    1

    1000000000000

    Returns: 2

  312. 2

    2

    50

    5

    Returns: 2

  313. 1

    1

    66

    100000000000

    Returns: 183

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: