Statistics

Problem Statement for "KitayutaMart"

Problem Statement

This problem statement contains superscripts that may not display properly outside the applet.

Kitayuta Mart is the largest supermarket in Shuseki Kingdom, offering a great variety of food and household products. The main products are fruits, especially apples. The store sells K kinds of apples, numbered from 1 to K. The price system is a little special: the original price of an apple of kind i (1 <= i <= K) is i yen (the currency of the kingdom). However, if a customer wants to buy more than one apple of kind i, the second apple will cost 2*i yen, the third apple will cost 22*i yen, and so on. In general, if a customer is buying n apples of kind i, the actual price of the j-th (1 <= j <= n) apple will be 2j-1*i yen. The store has a sufficient supply of each kind of apples.

Lun the dog loves apples. She wants to buy N apples at Kitayuta Mart. The kinds of apples does not matter to her, thus she will choose N apples so that the total price calculated using the above formula is minimized. You are given two ints: N and K. Find and return the actual price (NOT the original price) of the apple with the highest actual price among the apples that she will buy modulo 1,000,000,007.

Definition

Class:
KitayutaMart
Method:
lastPrice
Parameters:
int, int
Returns:
int
Method signature:
int lastPrice(int N, int K)
(be sure your method is public)

Notes

  • It can be shown that the answer is unique.

Constraints

  • N will be between 1 and 1,000,000,000, inclusive.
  • K will be between 1 and 1,000,000,000, inclusive.

Examples

  1. 3

    1

    Returns: 4

    The store sells only one kind of apples. Their original price is 1 yen. She will buy three of them, and the most expensive one will cost 22*1 = 4 yen.

  2. 3

    2

    Returns: 2

    In this case, another kind of apples is also on sale. Instead of buying three of kind 1, she can buy two of kind 1 and one of kind 2. Their costs will be 1, 2, and 2 yen, so the most expensive apple in this case only costs 2 yen.

  3. 5

    3

    Returns: 4

    This time, yet another kind of apples is available, and she needs five apples. There are two options: two of kind 1, two of kind 2, one of kind 3 three of kind 1, one of kind 2, one of kind 3 In either way, she will have to pay 4 yen for the most expensive apple.

  4. 1000000000

    1

    Returns: 570312504

    In this extreme case, the price of an apple will reach 2999999999 yen.

  5. 987654321

    876543210

    Returns: 493827168

  6. 1

    1

    Returns: 1

  7. 2

    1

    Returns: 2

  8. 2

    1000000000

    Returns: 2

  9. 3

    3

    Returns: 2

  10. 4

    2

    Returns: 4

  11. 4

    3

    Returns: 3

  12. 4

    4

    Returns: 3

  13. 4

    82373

    Returns: 3

  14. 5

    338841143

    Returns: 4

  15. 10

    469795038

    Returns: 6

  16. 15

    3920567

    Returns: 8

  17. 15

    385467295

    Returns: 8

  18. 35

    63

    Returns: 19

  19. 36

    63

    Returns: 20

  20. 37

    63

    Returns: 20

  21. 38

    63

    Returns: 20

  22. 39

    63

    Returns: 21

  23. 40

    63

    Returns: 22

  24. 41

    63

    Returns: 22

  25. 64

    96859931

    Returns: 33

  26. 79

    25659510

    Returns: 41

  27. 81

    7

    Returns: 7168

  28. 90

    63

    Returns: 48

  29. 91

    63

    Returns: 48

  30. 92

    63

    Returns: 48

  31. 93

    63

    Returns: 48

  32. 94

    63

    Returns: 48

  33. 183

    327

    Returns: 94

  34. 322

    373

    Returns: 163

  35. 322

    2636

    Returns: 163

  36. 564

    39689

    Returns: 284

  37. 654

    746989317

    Returns: 329

  38. 848

    46620

    Returns: 427

  39. 873

    4383

    Returns: 440

  40. 3472

    297492278

    Returns: 1740

  41. 7327

    4764

    Returns: 3667

  42. 10000

    1000000000

    Returns: 5004

  43. 23623

    84733

    Returns: 11816

  44. 27076

    346164451

    Returns: 13542

  45. 32832

    73232

    Returns: 16418

  46. 44789

    1682840

    Returns: 22400

  47. 55574

    49388

    Returns: 27792

  48. 58933

    670227306

    Returns: 29472

  49. 64281

    40524

    Returns: 32145

  50. 91374

    816110416

    Returns: 45692

  51. 247051

    954209858

    Returns: 123530

  52. 750758

    373855410

    Returns: 375384

  53. 2393627

    1674

    Returns: 999026502

  54. 2906682

    616531489

    Returns: 1453346

  55. 6114416

    133017382

    Returns: 3057215

  56. 6240730

    452262198

    Returns: 3120372

  57. 7368841

    959584

    Returns: 51563072

  58. 7661137

    717023

    Returns: 309232640

  59. 8647499

    95668

    Returns: 263685741

  60. 10198783

    37

    Returns: 527266470

  61. 22057479

    7966

    Returns: 26570049

  62. 66442405

    11860

    Returns: 326332281

  63. 72884870

    611802957

    Returns: 36442440

  64. 82364646

    38

    Returns: 991486540

  65. 104086214

    801456050

    Returns: 52043114

  66. 148371534

    7587706

    Returns: 711113665

  67. 151403858

    302852177

    Returns: 75701936

  68. 178275374

    10

    Returns: 459365159

  69. 211961529

    708865200

    Returns: 105980770

  70. 291388018

    836522883

    Returns: 145694016

  71. 298984849

    807370501

    Returns: 149492432

  72. 300735188

    16

    Returns: 211686802

  73. 303154838

    41

    Returns: 258309882

  74. 320861287

    949502693

    Returns: 160430652

  75. 360621153

    177

    Returns: 163701177

  76. 368712057

    110

    Returns: 3535305

  77. 370061683

    20479689

    Returns: 695831235

  78. 406486383

    712020460

    Returns: 203243200

  79. 408297065

    81205484

    Returns: 667801152

  80. 410442627

    99863879

    Returns: 443404032

  81. 423728044

    680589140

    Returns: 211864029

  82. 431793980

    1900877

    Returns: 69622281

  83. 439165413

    31273839

    Returns: 552208989

  84. 484800872

    817752860

    Returns: 242400445

  85. 517082547

    194971110

    Returns: 322111452

  86. 545040495

    349226636

    Returns: 272520255

  87. 558427013

    2

    Returns: 668111021

  88. 600229478

    14507012

    Returns: 528641740

  89. 618973530

    925332874

    Returns: 309486772

  90. 623452241

    58579054

    Returns: 637636440

  91. 633916535

    2489209

    Returns: 327615069

  92. 675068807

    224155941

    Returns: 453513872

  93. 692701178

    50

    Returns: 474348601

  94. 697361880

    4

    Returns: 325753967

  95. 712384807

    352584036

    Returns: 359800788

  96. 721501126

    551

    Returns: 851184460

  97. 722210475

    704387675

    Returns: 361105244

  98. 739014523

    184176866

    Returns: 745935752

  99. 759893834

    5208

    Returns: 461628898

  100. 784916702

    230290042

    Returns: 648673276

  101. 811409044

    41

    Returns: 156042987

  102. 818575853

    10

    Returns: 22982012

  103. 820283378

    21438417

    Returns: 510681560

  104. 821005795

    306077643

    Returns: 514928168

  105. 835228347

    246071042

    Returns: 686172552

  106. 845990695

    772528466

    Returns: 422995356

  107. 851433670

    750005226

    Returns: 425716844

  108. 864042774

    207433349

    Returns: 966970968

  109. 917937478

    240749374

    Returns: 872877488

  110. 429865193

    119075969

    Returns: 383426548

  111. 999999995

    63

    Returns: 79765447

  112. 999999996

    63

    Returns: 267558083

  113. 999999997

    63

    Returns: 267558083

  114. 999999998

    63

    Returns: 267558083

  115. 999999999

    63

    Returns: 455350719

  116. 1000000000

    63

    Returns: 643143355

  117. 1000000000

    268435454

    Returns: 926258212

  118. 1000000000

    268435455

    Returns: 926258208

  119. 1000000000

    268435456

    Returns: 926258208

  120. 1000000000

    500000005

    Returns: 500000010

  121. 1000000000

    500000006

    Returns: 500000008

  122. 1000000000

    900000000

    Returns: 500000008

  123. 1000000000

    999999997

    Returns: 500000008

  124. 1000000000

    999999998

    Returns: 500000008

  125. 1000000000

    999999999

    Returns: 500000008

  126. 1000000000

    22222

    Returns: 421001024

  127. 1000000000

    1000000000

    Returns: 500000008

  128. 31321321

    24234

    Returns: 552632306

  129. 1000000000

    8374

    Returns: 510978640

  130. 10000000

    1000000

    Returns: 256002048

  131. 7

    3

    Returns: 6

  132. 999999000

    100000

    Returns: 999103491

  133. 1

    33

    Returns: 1

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: