Statistics

Problem Statement for "MinskyMystery"

Problem Statement

Marvin plays a simple game. The game is played with an infinite supply of marbles and five bags, labeled "bag 0" through "bag 4".

At the beginning, Marvin takes N marbles (where N is a nonnegative integer) and places them into bag 0. The remaining four bags are left empty. Marvin then follows this simple algorithm: 

    Add a marble into bag 1.
    Repeat forever:
        Add a marble into bag 1.
        Empty bag 4.
        While there are marbles in bag 0:
            While there are marbles both in bag 0 and in bag 1:
                Remove a marble from bag 0.
                Remove a marble from bag 1.
                Add a marble into bag 2.
                Add a marble into bag 3.
            End While
            Add a marble into bag 4.
            If bags 0 and 1 are both empty:
                Move all marbles from bag 3 to bag 4.
                TERMINATE THE GAME
            End If
            Move all marbles from bag 3 to bag 1.
        End While
        Move all marbles from bag 2 to bag 0.
    End Repeat

You are given a long N. Count the number of times a marble enters a bag during Marvin's game. That is, compute X+Y, where X is the number of times a marble is added to some bag, and Y is the number of times a marble is moved from one bag to another. To avoid overflows, return just the value ((X+Y) modulo 1,000,000,009). If Marvin's game does not terminate for the given N, return -1 instead.

Definition

Class:
MinskyMystery
Method:
computeAnswer
Parameters:
long
Returns:
int
Method signature:
int computeAnswer(long N)
(be sure your method is public)

Notes

  • Suppose there are M marbles in bag A. The instruction "Move all marbles from bag A to bag B." then counts as M individual moves.
  • Note that N is allowed to be zero.

Constraints

  • N will be between 0 and 10^12, inclusive.

Examples

  1. 2

    Returns: 9

  2. 3

    Returns: 27

  3. 4

    Returns: 16

  4. 2401

    Returns: 59058

  5. 0

    Returns: -1

  6. 1

    Returns: -1

  7. 5

    Returns: 88

  8. 6

    Returns: 23

  9. 7

    Returns: 182

  10. 8

    Returns: 30

  11. 9

    Returns: 74

  12. 10

    Returns: 37

  13. 11

    Returns: 467

  14. 12

    Returns: 44

  15. 13

    Returns: 659

  16. 14

    Returns: 51

  17. 15

    Returns: 121

  18. 16

    Returns: 58

  19. 17

    Returns: 1138

  20. 18

    Returns: 65

  21. 19

    Returns: 1426

  22. 20

    Returns: 72

  23. 21

    Returns: 168

  24. 22

    Returns: 79

  25. 23

    Returns: 2098

  26. 24

    Returns: 86

  27. 25

    Returns: 414

  28. 26

    Returns: 93

  29. 27

    Returns: 215

  30. 28

    Returns: 100

  31. 29

    Returns: 3349

  32. 30

    Returns: 107

  33. 999999974243

    Returns: 997345690

  34. 999966000289

    Returns: 895616073

  35. 999932000987

    Returns: 846407291

  36. 549697684831

    Returns: 240454710

  37. 999992456923

    Returns: 117902564

  38. 999985999949

    Returns: 342769624

  39. 999663912463

    Returns: 789183514

  40. 549755813888

    Returns: 145331294

  41. 998295347921

    Returns: 422523484

  42. 990728680597

    Returns: 897820809

  43. 991325085943

    Returns: 642918241

  44. 990132634063

    Returns: 459197756

  45. 23899065817

    Returns: 336739667

  46. 501286585121

    Returns: 69264569

  47. 79418294653

    Returns: 188092387

  48. 857742881383

    Returns: 714172553

  49. 847288609443

    Returns: 94047574

  50. 961346991611

    Returns: 515658070

  51. 289721913119

    Returns: 483988869

  52. 1000000000000

    Returns: 999968511

  53. 56604

    Returns: 198116

  54. 639

    Returns: 5009

  55. 940489420

    Returns: 291712945

  56. 181681

    Returns: 70339234

  57. 2509315

    Returns: 40860019

  58. 61008809

    Returns: 256153748

  59. 307882

    Returns: 1077589

  60. 9657166375

    Returns: 250857733

  61. 632511669

    Returns: 954674708

  62. 1140

    Returns: 3992

  63. 473785794118

    Returns: 250264493

  64. 85426

    Returns: 298993

  65. 823

    Returns: 2711674

  66. 9691

    Returns: 397540

  67. 32677176439

    Returns: 874505132

  68. 66634240

    Returns: 233219842

  69. 8742164973

    Returns: 480291680

  70. 7740

    Returns: 27092

  71. 35679235033

    Returns: 709535439

  72. 912

    Returns: 3194

  73. 62058

    Returns: 217205

  74. 68313523682

    Returns: 97330738

  75. 167483122

    Returns: 586190929

  76. 73316810814

    Returns: 608835547

  77. 25780653

    Returns: 201948452

  78. 50123

    Returns: 49610115

  79. 95066

    Returns: 332733

  80. 1141118

    Returns: 3993915

  81. 641536

    Returns: 2245378

  82. 1303791137

    Returns: 481352061

  83. 934

    Returns: 3271

  84. 3979

    Returns: 357087

  85. 8544095

    Returns: 139126353

  86. 1716

    Returns: 6008

  87. 708

    Returns: 2480

  88. 37222940

    Returns: 130280292

  89. 255270

    Returns: 893447

  90. 194934

    Returns: 682271

  91. 35020

    Returns: 122572

  92. 4921

    Returns: 121032

  93. 22198161106

    Returns: 693563180

  94. 793869339907

    Returns: 515090730

  95. 455750691863

    Returns: 915291204

  96. 88458156143

    Returns: 438777579

  97. 743531953133

    Returns: 489686193

  98. 67336661975

    Returns: 465302635

  99. 55858966335

    Returns: 561899028

  100. 462398666113

    Returns: 16325919

  101. 414917635852

    Returns: 211712416

  102. 80399258354

    Returns: 397401712

  103. 804762276120

    Returns: 667941078

  104. 41071462606

    Returns: 750117836

  105. 411282164164

    Returns: 487561625

  106. 80052724013

    Returns: 350513123

  107. 657164428388

    Returns: 75478660

  108. 253690000746

    Returns: 914994630

  109. 63345060786

    Returns: 707710764

  110. 86775214293

    Returns: 739172521

  111. 703837870306

    Returns: 432523906

  112. 86567864778

    Returns: 987524007

  113. 84631031817

    Returns: 943076612

  114. 636455831109

    Returns: 570632159

  115. 132336486706

    Returns: 177699306

  116. 72724370282

    Returns: 535293703

  117. 661765556521

    Returns: 896568724

  118. 475808264703

    Returns: 164706634

  119. 45572770802

    Returns: 504696378

  120. 257935587385

    Returns: 51110126

  121. 29460618561

    Returns: 774843328

  122. 866070866297

    Returns: 156898751

  123. 47539168631

    Returns: 105722591

  124. 33346970931

    Returns: 217936614

  125. 234250059026

    Returns: 875199222

  126. 456203051683

    Returns: 650221118

  127. 655050458446

    Returns: 676583935

  128. 154332755733

    Returns: 939909040

  129. 97860137303

    Returns: 438301685

  130. 948237557684

    Returns: 831422034

  131. 72541902122

    Returns: 896655152

  132. 375775526335

    Returns: 878098766

  133. 999999999961

    Returns: 779047676

  134. 99999999977

    Returns: 290123875

  135. 999999999989

    Returns: 777026814

  136. 99999999999

    Returns: 333326282

  137. 999999989987

    Returns: 897960007

  138. 1000000009

    Returns: 877697702

  139. 68718952447

    Returns: 91912188

  140. 22801763489

    Returns: 177598378

  141. 947147262401

    Returns: 458754656

  142. 1000023281

    Returns: 44457138

  143. 982451653

    Returns: 746253085

  144. 999999999937

    Returns: 780784928

  145. 298850081953

    Returns: 249982808

  146. 100000099963

    Returns: 542875400

  147. 900092400000

    Returns: 323371652

  148. 999999999999

    Returns: 333262832

  149. 3367900313

    Returns: 814911882

  150. 274876858367

    Returns: 880140535

  151. 733925199079

    Returns: 886314019

  152. 1000000007

    Returns: 877697580

  153. 99988877612

    Returns: 961068503

  154. 999999937

    Returns: 877717060

  155. 4294967297

    Returns: 767219451

  156. 200000000041

    Returns: 215245476

  157. 200560490131

    Returns: 632944746

  158. 27644437

    Returns: 928053176

  159. 9997954969

    Returns: 841019510

  160. 896767806551

    Returns: 652961229

  161. 999999899533

    Returns: 381838114

  162. 999990000017

    Returns: 163550762

  163. 999999999091

    Returns: 844964456

  164. 32416190071

    Returns: 534118777

  165. 987014682601

    Returns: 681966847

  166. 999999999959

    Returns: 779192194

  167. 100000003591

    Returns: 315762591

  168. 7427466391

    Returns: 968995645

  169. 59999999999

    Returns: 323663620

  170. 3214745587

    Returns: 510206106

  171. 3214747044

    Returns: 251614557

  172. 199199199203

    Returns: 6626450

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: