Statistics

Problem Statement for "BearPlays"

Problem Statement

Limak is a little bear who loves to play. Today he is playing by moving some stones between two piles of stones. Initially, one of the piles has A and the other has B stones in it.


Limak has decided to perform a sequence of K operations. In each operation he will double the size of the currently smaller pile. Formally, if the current pile sizes are labeled X and Y in such a way that X <= Y, he will move X stones from the second pile to the first one. After this move the new pile sizes will be X+X and Y-X.


You are given the ints A, B, and K. Determine the pile sizes after Limak finishes all his operations. Return the size of the smaller of those piles.


Formally, suppose that the final pile sizes are labeled P and Q in such a way that P <= Q. Return P.

Definition

Class:
BearPlays
Method:
pileSize
Parameters:
int, int, int
Returns:
int
Method signature:
int pileSize(int A, int B, int K)
(be sure your method is public)

Notes

  • Pay attention to the unusual time limit.

Constraints

  • A and B will be between 1 and 1,000,000,000, inclusive.
  • K will be between 1 and 2,000,000,000, inclusive.

Examples

  1. 4

    7

    2

    Returns: 5

    The process will look as follows: Initially, the pile sizes are 4 and 7. First operation: Limak doubles the pile of size 4 by moving 4 stones from the other pile to this pile. The new pile sizes are 8 and 3. Second operation: Limak doubles the pile of size 3. The final pile sizes are 5 and 6. As 5 <= 6, the correct return value is 5.

  2. 5

    5

    3

    Returns: 0

    The initial pile sizes are 5 and 5. In the first operation Limak will double one of them, so after the operation the new pile sizes will be 10 and 0. The second and third operation do nothing: in each of them Limak doubles the size of an empty pile. As 0 ≤ 10, the correct return value is 0.

  3. 2

    6

    1

    Returns: 4

    After the only operation the pile sizes will be 4 and 4, hence the correct return value is 4.

  4. 2

    8

    2000000000

    Returns: 2

  5. 900000000

    350000000

    3

    Returns: 300000000

  6. 1

    1

    1

    Returns: 0

  7. 14

    7

    1999999995

    Returns: 7

  8. 25

    175

    123789

    Returns: 0

  9. 12

    19988

    1999990127

    Returns: 8736

  10. 123

    222

    10000

    Returns: 108

  11. 23842

    963812

    123456

    Returns: 27916

  12. 990592741

    995283456

    2

    Returns: 9381430

  13. 997283279

    974845622

    2

    Returns: 44875314

  14. 960146777

    896804300

    1999916049

    Returns: 464229233

  15. 985003573

    985003584

    1997000978

    Returns: 944658413

  16. 490044323

    980088648

    1982385059

    Returns: 583170464

  17. 864000001

    432000010

    1994199464

    Returns: 380679039

  18. 53523743

    643643144

    1783815875

    Returns: 79846988

  19. 682599717

    229233697

    1791474505

    Returns: 444168792

  20. 633529762

    183169449

    1675389893

    Returns: 336598032

  21. 212580698

    108313881

    1596161260

    Returns: 25052817

  22. 469976352

    113801075

    1975807810

    Returns: 160654906

  23. 232315727

    564541170

    1192349580

    Returns: 78625352

  24. 469283710

    367103170

    1253520177

    Returns: 271024320

  25. 107314436

    397961508

    1073185315

    Returns: 70019824

  26. 13607425

    26757382

    1908346922

    Returns: 3077231

  27. 633238026

    75774216

    1748527448

    Returns: 219347358

  28. 855122520

    935996040

    1695613548

    Returns: 668626560

  29. 587532000

    334554000

    1863416726

    Returns: 66858000

  30. 975196530

    61704720

    1922344248

    Returns: 111912570

  31. 177119712

    961318512

    1502015128

    Returns: 270713520

  32. 162673792

    911068032

    3

    Returns: 227648512

  33. 144000432

    929741392

    25

    Returns: 536870912

  34. 120567088

    953174736

    26

    Returns: 0

  35. 614411264

    794874880

    5

    Returns: 68845568

  36. 692810752

    716475392

    1876543211

    Returns: 671088640

  37. 1024

    128128

    1999016742

    Returns: 31104

  38. 999999999

    999999997

    2000000000

    Returns: 710117452

  39. 999999937

    2

    2000000000

    Returns: 441221215

  40. 837936763

    123900852

    2000000000

    Returns: 281065208

  41. 123456789

    978546879

    1000000000

    Returns: 373885632

  42. 7

    1000000000

    2000000000

    Returns: 374755862

  43. 999999987

    999999986

    2000000000

    Returns: 134217728

  44. 997123733

    993117317

    2000000000

    Returns: 28245992

  45. 999999150

    1

    1999999150

    Returns: 393839025

  46. 54545454

    8778787

    2000000000

    Returns: 10313303

  47. 1000000000

    3

    2000000000

    Returns: 90958542

  48. 333234427

    834233242

    1290000004

    Returns: 539127008

  49. 980402471

    856093703

    2000000000

    Returns: 437246368

  50. 1

    100000002

    2000000000

    Returns: 8445655

  51. 44105206

    56045893

    2000000000

    Returns: 40009044

  52. 999999992

    1

    2000000000

    Returns: 338667947

  53. 900000000

    900000001

    900000000

    Returns: 513839102

  54. 673351051

    906797945

    2000000000

    Returns: 369638348

  55. 1

    900000001

    2000000000

    Returns: 315873084

  56. 1

    999999996

    999999995

    Returns: 269563181

  57. 3

    1000000000

    2000000000

    Returns: 90958542

  58. 3

    1000000000

    1000000000

    Returns: 46904304

  59. 4993

    9504729

    2000000

    Returns: 4271300

  60. 2263846

    823749379

    2000000000

    Returns: 281712054

  61. 980000000

    980000001

    980000000

    Returns: 760098087

  62. 1000000000

    999999999

    999999999

    Returns: 322564261

  63. 999999996

    999999997

    2000000000

    Returns: 489248433

  64. 1000000000

    99999999

    2000000000

    Returns: 174522464

  65. 932984238

    935838787

    989149348

    Returns: 321897353

  66. 744583339

    133062956

    2000000000

    Returns: 177995929

  67. 999999999

    1000000000

    2000000000

    Returns: 211999778

  68. 999999937

    999999761

    2000000000

    Returns: 695746094

  69. 1000000000

    999999999

    1000000000

    Returns: 645128522

  70. 1236

    755523441

    1126626789

    Returns: 371285664

  71. 273704458

    291906285

    1467314700

    Returns: 120427278

  72. 999999937

    500

    2000000000

    Returns: 17581259

  73. 424238335

    957747792

    2000000000

    Returns: 521460786

  74. 1000000000

    12676543

    1234134410

    Returns: 249638011

  75. 7918469

    797264985

    500000000

    Returns: 84967022

  76. 1000000000

    9

    2000000000

    Returns: 23452759

  77. 1

    980514946

    2000000000

    Returns: 82099243

  78. 1000000000

    7

    1000000000

    Returns: 15625000

  79. 1

    999999999

    1999999999

    Returns: 106445312

  80. 1000000000

    7

    2000000000

    Returns: 374755862

  81. 1000000000

    999999999

    2000000000

    Returns: 211999778

  82. 804289384

    846930887

    2000000000

    Returns: 155828687

  83. 874856466

    719677331

    2000000000

    Returns: 280424418

  84. 900000001

    350000000

    338428742

    Returns: 580334189

  85. 15

    1000000000

    2000000000

    Returns: 186079065

  86. 1231231

    234234234

    2000000000

    Returns: 66154249

  87. 1

    999999928

    1900000000

    Returns: 454161303

  88. 470211272

    470211273

    470211272

    Returns: 2

  89. 984943659

    144108931

    470211273

    Returns: 496251738

  90. 1

    1000000000

    2000000000

    Returns: 224136384

  91. 666666337

    333333331

    2000000000

    Returns: 50005696

  92. 2

    5

    1

    Returns: 3

  93. 999995239

    999995093

    2000000000

    Returns: 169540052

  94. 999999893

    999999929

    2000000000

    Returns: 658478668

  95. 421414151

    121515

    2000000000

    Returns: 56234616

  96. 999999999

    999999998

    1999999999

    Returns: 29534154

  97. 1

    124132453

    2000000000

    Returns: 49958608

  98. 1000000000

    999999973

    2000000000

    Returns: 376121290

  99. 123456789

    876543218

    2000000000

    Returns: 436797722

  100. 256898537

    234575198

    1973594324

    Returns: 135593697

  101. 1000000000

    3456

    2000000000

    Returns: 381336192

  102. 1000000000

    1

    2000000000

    Returns: 224136384

  103. 132658732

    238957692

    2000000000

    Returns: 4004240

  104. 1000000000

    499999999

    2000000000

    Returns: 587209205

  105. 2

    1000000000

    2000000000

    Returns: 281285210

  106. 1

    999999997

    2000000000

    Returns: 289882546

  107. 11

    787231134

    1000000000

    Returns: 154427694

  108. 954899097

    636807826

    2000000000

    Returns: 779598833

  109. 4

    16

    2

    Returns: 4

  110. 1

    9

    2000000000

    Returns: 4

  111. 999999999

    1000000000

    1987654321

    Returns: 884105863

  112. 1

    999999936

    2000000000

    Returns: 491900853

  113. 42

    468

    1334

    Returns: 138

  114. 1000000000

    999999

    2000000000

    Returns: 329304471

  115. 999987301

    999999929

    2000000000

    Returns: 96495974

  116. 876543210

    1

    1000000000

    Returns: 48285169

  117. 234525412

    38291389

    2000000000

    Returns: 14053634

  118. 11

    29

    112

    Returns: 16

  119. 982451653

    982451629

    2000000000

    Returns: 680880180

  120. 942935561

    40821488

    1722874736

    Returns: 22410468

  121. 2

    998834797

    2000000000

    Returns: 130020292

  122. 500000001

    1000000000

    2000000000

    Returns: 129954343

  123. 3

    5

    1

    Returns: 2

  124. 999999999

    123456789

    1000000000

    Returns: 75162132

  125. 114514810

    919191919

    2000000000

    Returns: 508471631

  126. 912719116

    381101710

    1000000000

    Returns: 312869686

  127. 987654329

    12345678

    1000000000

    Returns: 31057099

  128. 987654321

    123456789

    123456789

    Returns: 186572358

  129. 701687787

    458299111

    2000000000

    Returns: 76428172

  130. 654958441

    99999999

    2000000000

    Returns: 298540776

  131. 967406281

    623426812

    1802419701

    Returns: 499154784

  132. 3

    4

    1

    Returns: 1

  133. 8

    999999999

    500000002

    Returns: 4

  134. 740843895

    546119731

    2000000000

    Returns: 285167086

  135. 997999999

    999997789

    2000000000

    Returns: 259788284

  136. 314090195

    145459798

    670960532

    Returns: 115098379

  137. 1000000000

    3457

    2000000000

    Returns: 32401724

  138. 16

    999999991

    2000000000

    Returns: 285156252

  139. 900000001

    350000000

    453454547

    Returns: 557932576

  140. 723456789

    987321654

    2000000000

    Returns: 772049718

  141. 301413356

    336971124

    2000000000

    Returns: 252554624

  142. 982451653

    32452843

    2000000000

    Returns: 128738688

  143. 5000

    999999002

    2000000000

    Returns: 34874126

  144. 1

    1

    2

    Returns: 0

  145. 1

    1

    2000000000

    Returns: 0

  146. 999999998

    1000000000

    1

    Returns: 2

  147. 500000003

    500000004

    2000000000

    Returns: 116088868

  148. 999999998

    999999999

    2000000000

    Returns: 59068308

  149. 900000001

    350000000

    999999999

    Returns: 509105161

  150. 984756312

    748512347

    2000000000

    Returns: 53083530

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: