Statistics

Problem Statement for "EllysTeleport"

Problem Statement

Elly plays a platform game on her computer. There are N platforms with distinct heights, placed on top of each other. You can generate the heights of the platforms as follows:

  • Platform number 1 is has height[1] = H1.
  • For each i between 2 and N, inclusive, height[i] = (height[i-1] * A + B) % M.

The girl has a "hero" whom she can move from platform to platform. At the beginning of the game there is a coin on each platform. The hero collects the coin the first time she visits the platform. (Once a coin is collected, it is gone. Visiting the same platform again does not give Elly a second coin.)

In the beginning of the game Elly can place her hero on any of the N platforms. Once she does that, the hero will pick up the coin from that platform and then the game starts.

During the game Elly only has one way to move her hero: by using a device that teleports the hero vertically. The device is deterministic and it behaves as follows: if the hero's current platform is at height X, the hero gets teleported to the height Y = (X * P + Q) % M. After the teleport, one of three different things will happen:

  • If there is a platform at height Y, the hero will stand on that platform and collect the coin from that platform (if it is still there).
  • If there is no platform at height Y but there are some lower platforms, the hero falls down until she hits the closest platform. She will always lands safely, regardless of the height of the fall. Then, she will collect the coin from that platform (if it is still there).
  • If there are no platforms at or below the hero's new height, the game ends.

Elly can use the device arbitrarily many times, one after another. Note that the device can only be used while the hero is standing on a platform (i.e., not while she is falling).

You are given all the ints mentioned in the problem statement. Compute and return the largest number of coins Elly's hero can collect during a single game.

Definition

Class:
EllysTeleport
Method:
getMax
Parameters:
int, int, int, int, int, int, int
Returns:
int
Method signature:
int getMax(int N, int H1, int A, int B, int P, int Q, int M)
(be sure your method is public)

Constraints

  • N will be between 1 and 10,000, inclusive.
  • M will be between 1 and 1,000,000,007, inclusive.
  • H1, A, B, P and Q will be between 0 and M-1, inclusive.
  • All platform heights will be distinct.

Examples

  1. 11

    9

    17

    9

    7

    13

    23

    Returns: 6

    The generated heights are {9, 1, 3, 14, 17, 22, 15, 11, 12, 6, 19}. The optimal choice would be to start from the platform with height 15. The heights Elly's hero will visit are: 15 -> 3 -> 11 -> [21] -> 19 -> [8] -> 6 -> 9 -> [7] -> 6... With [Y] we have denoted a height where the hero is teleported to, but there is no platform so she starts falling down.

  2. 8

    17

    23

    19

    15

    28

    43

    Returns: 4

    The generated numbers are {17, 23, 32, 24, 12, 37, 10, 34}. There are two possible choices for a starting platform, which yields the maximal number of coins: 32 or 12 (the paths being, respectively, 32 -> [35] -> 34 -> [22] -> 17 -> [25] -> 24 -> [1] -> game ends, and 12 -> [36] -> 34 -> [22] -> 17 -> [25] -> 24 -> [1] -> game ends).

  3. 15

    42

    114

    52

    76

    1

    131

    Returns: 5

    The generated numbers are {42, 124, 40, 27, 117, 28, 100, 55, 34, 129, 86, 31, 49, 5, 98}.

  4. 10

    71

    54

    85

    96

    52

    100

    Returns: 10

    Here the heights are {71, 19, 11, 79, 51, 39, 91, 99, 31, 59}. Starting from the platform with height 99 Elly's hero can collect all of the coins: 99 -> [56] -> 51 -> [49] -> 39 -> [96] -> 91 -> [88] -> 79 -> [36] -> 31 -> [28] -> 19 -> [76] -> 71 -> [68] -> 59 -> [16] -> 11 -> [8] -> game ends

  5. 1000

    1337

    706135

    1085680

    1153206

    345473

    1234567

    Returns: 42

    Watch out for overflows when generating the heights!

  6. 10

    581869302

    404620562

    708632711

    545404204

    133711905

    795755685

    Returns: 5

  7. 20

    205238249

    90813526

    207423799

    46884967

    84433391

    372047868

    Returns: 7

  8. 50

    24531490

    180862451

    30574576

    182506777

    15198492

    196140734

    Returns: 14

  9. 100

    138749190

    73732609

    121894487

    126303053

    81133257

    150802600

    Returns: 18

  10. 200

    103919524

    61040475

    131262539

    121922632

    171932465

    183966551

    Returns: 26

  11. 500

    20544909

    592656503

    483031418

    361913170

    328410175

    609397213

    Returns: 46

  12. 1000

    522136403

    173978709

    346827080

    586119708

    867889990

    892462744

    Returns: 78

  13. 2000

    17940960

    34462715

    143305596

    130116355

    141506394

    153380496

    Returns: 42

  14. 5000

    193280970

    280854272

    354267637

    343593670

    139963091

    379821983

    Returns: 92

  15. 10000

    443648354

    110506748

    62143011

    50639018

    612104790

    684602216

    Returns: 232

  16. 1

    42

    42

    42

    42

    42

    1337

    Returns: 1

  17. 10000

    262522450

    1

    1

    17

    42

    1000000007

    Returns: 2

  18. 10000

    870676135

    1

    1

    1337

    666

    1000000007

    Returns: 1

  19. 10000

    136721026

    1

    1

    1234567

    7654321

    1000000007

    Returns: 2

  20. 10000

    359573801

    1

    1

    421337

    123456789

    1000000007

    Returns: 2

  21. 10000

    2

    1

    2

    1

    1

    10001

    Returns: 10000

  22. 10000

    100001

    1

    179351

    1

    133742

    999981825

    Returns: 8850

  23. 10000

    169163754

    1

    1

    1

    189375145

    189375146

    Returns: 10000

  24. 10000

    45525813

    1

    2

    1

    198304612

    198304613

    Returns: 10000

  25. 10000

    25475623

    1

    5

    1

    417177801

    417177802

    Returns: 10000

  26. 10000

    6676782

    1

    13

    1

    758242871

    758242872

    Returns: 10000

  27. 10000

    226954798

    1

    17

    1

    310701080

    310701081

    Returns: 10000

  28. 10000

    290822200

    1

    42

    1

    361931884

    361931885

    Returns: 10000

  29. 10000

    182911688

    1

    213794687

    1

    1

    213794688

    Returns: 10000

  30. 10000

    113300187

    1

    147944787

    1

    2

    147944789

    Returns: 10000

  31. 10000

    540721923

    1

    884392667

    1

    5

    884392672

    Returns: 10000

  32. 10000

    264060007

    1

    638781080

    1

    13

    638781093

    Returns: 10000

  33. 10000

    7041753

    1

    7097687

    1

    17

    7097704

    Returns: 10000

  34. 10000

    156513983

    1

    879609673

    1

    42

    879609715

    Returns: 10000

  35. 10000

    49993

    1

    5

    1

    6

    49994

    Returns: 10000

  36. 10000

    49993

    1

    5

    1

    100

    49994

    Returns: 10000

  37. 10000

    999899998

    1

    100000

    1

    42424242

    999899999

    Returns: 10000

  38. 10000

    0

    1

    100000

    1

    100000

    999899999

    Returns: 10000

  39. 10000

    2

    1

    100000

    1

    100003

    999900001

    Returns: 10000

  40. 10000

    999800000

    1

    999799999

    1

    100000

    999899999

    Returns: 10000

  41. 10000

    999800000

    1

    999799999

    1

    999899990

    999899999

    Returns: 10000

  42. 10000

    0

    1

    100000

    1

    999799999

    999899999

    Returns: 10000

  43. 10000

    150263527

    498298617

    361825002

    308554712

    488869153

    802611721

    Returns: 127

  44. 10000

    365796717

    210120468

    339840185

    15464610

    307573909

    519074043

    Returns: 257

  45. 10000

    150577917

    77035793

    12105075

    182712069

    129405346

    185518675

    Returns: 85

  46. 10000

    132351904

    511091141

    561821923

    45221080

    272606466

    698412072

    Returns: 198

  47. 10000

    101725768

    78758356

    10627672

    52277464

    132286397

    172898400

    Returns: 149

  48. 10000

    76338300

    107034863

    767742621

    134360178

    769482973

    961264979

    Returns: 160

  49. 10000

    13583447

    73472441

    65812705

    102871994

    110903855

    121898320

    Returns: 252

  50. 10000

    51357206

    21432300

    154326108

    70861390

    149146565

    174842016

    Returns: 163

  51. 10000

    347299895

    464776633

    175971016

    42901327

    49299350

    641212875

    Returns: 141

  52. 3643

    369786099

    4203888

    190222791

    58150106

    303810411

    427854494

    Returns: 75

  53. 9416

    397865508

    341201326

    147657059

    72059300

    193198051

    503168819

    Returns: 231

  54. 5580

    133505891

    53860493

    560738997

    290319951

    726585505

    949627106

    Returns: 173

  55. 1639

    179039632

    371368069

    366343581

    355650503

    527687642

    781277156

    Returns: 61

  56. 9234

    292490028

    184349496

    307398456

    7278837

    133348379

    375163522

    Returns: 134

  57. 5501

    317540307

    325791709

    23678544

    231714000

    658911095

    856191911

    Returns: 92

  58. 9164

    199661400

    32874570

    283421978

    150468287

    557942923

    748808120

    Returns: 208

  59. 7953

    844229571

    312240886

    811534968

    51119001

    320832263

    851888278

    Returns: 177

  60. 742

    27673078

    311415874

    214646562

    535321460

    667763804

    668894609

    Returns: 44

  61. 2697

    9782578

    13282903

    14756233

    13911552

    7324278

    24934750

    Returns: 54

  62. 3059

    102021547

    174383384

    412348616

    296873218

    159215731

    461232475

    Returns: 64

  63. 109

    265410014

    360010077

    375476813

    48387162

    253744890

    935061429

    Returns: 22

  64. 3199

    654458600

    339340132

    748110398

    191869111

    188361674

    897221240

    Returns: 109

  65. 2697

    13214088

    3735899

    10881188

    8743688

    6483088

    16601272

    Returns: 62

  66. 174

    22415547

    86218872

    19903848

    6160775

    119366415

    141230963

    Returns: 16

  67. 5511

    775197290

    563951939

    591775754

    362649214

    702384419

    784676681

    Returns: 100

  68. 3388

    497123320

    193529268

    239687779

    221752503

    614885118

    619011577

    Returns: 143

  69. 5344

    187447947

    13495705

    75760802

    365493589

    25781698

    383765657

    Returns: 122

  70. 5181

    156264919

    207707169

    133240619

    119032371

    92574779

    214072533

    Returns: 137

  71. 2084

    34763086

    622576118

    439820930

    631226552

    135070672

    933335694

    Returns: 60

  72. 852

    623269329

    857065948

    322457913

    592711182

    841692685

    884059690

    Returns: 54

  73. 7461

    41569465

    51608694

    173822100

    203376339

    107614289

    326274449

    Returns: 87

  74. 7946

    14649293

    126944086

    14255240

    78498592

    86271762

    126992369

    Returns: 244

  75. 3222

    42845045

    237137193

    205919137

    19089613

    228835099

    417831124

    Returns: 89

  76. 4081

    492229683

    482212588

    429265451

    518515435

    627638726

    958264126

    Returns: 111

  77. 7413

    221918251

    466198014

    49105784

    241078998

    425627456

    477612193

    Returns: 110

  78. 6165

    20135780

    57437844

    71338323

    102254516

    52424886

    171465366

    Returns: 107

  79. 8893

    193516735

    188400725

    1438085

    82229262

    45950561

    248890848

    Returns: 163

  80. 1189

    139006054

    181628626

    647438557

    228288551

    767965749

    869365981

    Returns: 69

  81. 3099

    19292622

    52471256

    62488250

    64233881

    25861987

    66157276

    Returns: 112

  82. 7550

    58519297

    10824443

    91078022

    40746576

    77371322

    109372427

    Returns: 246

  83. 6964

    263580362

    327106182

    290530998

    150954055

    671749885

    945581997

    Returns: 158

  84. 5597

    537294152

    534216451

    788174404

    40623875

    774634184

    807995101

    Returns: 107

  85. 7036

    183309798

    335959927

    204497431

    348432514

    413679405

    607956045

    Returns: 136

  86. 4946

    963306712

    334782891

    152295753

    384120460

    902769184

    969229186

    Returns: 217

  87. 7105

    129952823

    396839388

    464122393

    273096066

    771533956

    918921586

    Returns: 134

  88. 150

    225739419

    434797764

    323648778

    355975842

    412554788

    557543599

    Returns: 17

  89. 446

    601913200

    183140819

    232332505

    128154015

    219365083

    626114935

    Returns: 35

  90. 1432

    7121757

    11660224

    23092501

    28477947

    20579804

    42477422

    Returns: 67

  91. 9456

    324769810

    530715196

    182773470

    270789204

    110720767

    621457153

    Returns: 104

  92. 3164

    41456102

    32481049

    38989886

    42893612

    34722500

    79245770

    Returns: 102

  93. 4352

    222027819

    133820414

    634920763

    733185481

    192148983

    836506265

    Returns: 125

  94. 702

    150345485

    310618090

    475691096

    385787519

    329081921

    860483062

    Returns: 29

  95. 3835

    728252905

    793780050

    89611408

    408533132

    326283840

    847726654

    Returns: 111

  96. 50

    315454648

    326324656

    477253416

    210726130

    62061090

    523159177

    Returns: 9

  97. 5678

    574393398

    229031367

    419951882

    370752507

    180621093

    755438373

    Returns: 110

  98. 5960

    370004247

    719646637

    82080409

    724929116

    504304985

    870314537

    Returns: 111

  99. 7759

    107348298

    272289742

    159423158

    176503402

    114053590

    274213157

    Returns: 190

  100. 2573

    367287522

    27768175

    155036157

    293691766

    368477458

    486158241

    Returns: 59

  101. 1813

    12619163

    54568829

    44564660

    28718752

    56168076

    125500150

    Returns: 92

  102. 10000

    32423

    56547

    56234

    23434

    34634

    12345678

    Returns: 237

  103. 8192

    2

    5

    5

    9

    9

    8192

    Returns: 8192

  104. 10000

    942855823

    234992523

    123942342

    312499249

    194995959

    1000000007

    Returns: 232

  105. 10000

    948732532

    3125322

    34563

    23435

    3232654

    948732535

    Returns: 151

  106. 10000

    1

    1

    1

    1

    1

    1000000000

    Returns: 10000

  107. 10000

    0

    1

    1

    1

    1

    10000

    Returns: 10000

  108. 10000

    1000000005

    1000000002

    1000000003

    1000000004

    1000000001

    1000000006

    Returns: 235

  109. 2

    1

    1

    2

    1

    2

    1000

    Returns: 2

  110. 10000

    1

    1

    1

    1

    1

    100000

    Returns: 10000

  111. 10000

    0

    1

    1

    1

    17

    10000

    Returns: 10000

  112. 2

    91033541

    112603822

    118786616

    131388137

    52066666

    162379610

    Returns: 2

  113. 10000

    1

    1

    1

    1

    1

    1000000

    Returns: 10000

  114. 10000

    1000000000

    998244353

    504050000

    325346442

    345312262

    1000000007

    Returns: 112

  115. 10000

    1337

    706135

    1085680

    706135

    1085680

    12345679

    Returns: 10000

  116. 3

    1000000006

    1000005

    1000000004

    1000000003

    1000000002

    1000000007

    Returns: 1

  117. 10000

    1

    1

    1

    1

    1

    1000000007

    Returns: 10000

  118. 10000

    1

    1

    1

    371

    17

    10001

    Returns: 1224

  119. 10000

    1000000002

    1000000003

    1000000004

    1000000005

    1000000006

    1000000007

    Returns: 233

  120. 10000

    1

    1

    1

    1

    1

    10000000

    Returns: 10000

  121. 9999

    1

    1

    1

    1

    1

    1000000

    Returns: 9999

  122. 5

    1

    1

    1

    1

    10

    11

    Returns: 5

  123. 10000

    2

    1

    1

    1

    1000000006

    1000000007

    Returns: 10000

  124. 10000

    1

    1

    1

    1

    1000000006

    1000000007

    Returns: 10000

  125. 10000

    1337

    706135

    1085680

    1153206

    345473

    1234567

    Returns: 162

  126. 10000

    1000000006

    1000000000

    1000000004

    1000000003

    1000000002

    1000000007

    Returns: 170

  127. 10000

    1

    1

    1

    1

    1

    999999999

    Returns: 10000

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: