Statistics

Problem Statement for "EllysRain"

Problem Statement

Elly has a beautiful flowerpot with roses on her window sill. Whenever it rains outside, Elly remembers that she hasn't watered her roses in a while. However, now that it rains, maybe the rain will water them for her! To make sure the roses get watered properly, Elly watches the whole situation carefully and records where the individual raindrops fall.

For simplicity, we will consider the flowerpot to be a closed line segment of length L. (One endpoint of the segment has coordinate 0, the other has coordinate L, and both endpoints belong to the segment.) Each raindrop will fall onto some point of this segment. The coordinate of each raindrop will be an integer.

The flowerpot is considered properly watered if each possible closed interval of length D or more already received at least one raindrop. Note that this includes intervals that start and end at non-integer coordinates.

You are given the ints L and D. You are also given four other ints: N, P1, M, and A. These describe the rainfall. N drops fell onto our line segment. (The drops fell sequentially, i.e., one at a time.) The first raindrop landed on coordinate P1. For each of the following raindrops you can compute the coordinate where it dropped as follows: Let P_prev be the coordinate of the previous raindrop. Then the coordinate of the current raindrop is (P_prev * M + A) modulo (L + 1).

Find and return the smallest K such that Elly's flowerpot was properly watered after the first K raindrops. If the entire rainfall was not enough to water the flowerpot properly, return -1 instead.

Definition

Class:
EllysRain
Method:
getTime
Parameters:
int, int, int, int, int, int
Returns:
int
Method signature:
int getTime(int L, int D, int N, int P1, int M, int A)
(be sure your method is public)

Constraints

  • L will be between 2 and 1,000,000,000, inclusive.
  • D will be between 1 and L-1, inclusive.
  • N will be between 1 and 1,000,000, inclusive.
  • P1, M, and A will each be between 0 and L, inclusive.

Examples

  1. 23

    7

    12

    14

    13

    5

    Returns: 9

    We have a flowerpot of length L = 23, and we are waiting until each closed interval of length D = 7 or more gets hit by a raindrop. There are N = 12 raindrops. Using the formula from the problem statement we can compute that their coordinates are 14, 19, 12, 17, 10, 15, 8, 13, 6, 11, 4, 9 (in this order). First eight raindrops are not enough. For example, there is a completely dry interval of length 7.3 that starts at coordinate 0.4 and ends at coordinate 7.7. On the other hand, the first nine raindrops are already enough. Thus, the correct return value is 9.

  2. 10

    4

    5

    5

    2

    6

    Returns: -1

    This flowerpot has length 10. There are 5 raindrops, and each of them falls on the same coordinate: at 5. We need to water every interval of length 4 or more, but after the last raindrop the interval [6,10] is still all dry. Thus, the flowerpot is still not watered properly and we should return -1.

  3. 10

    5

    5

    5

    2

    6

    Returns: 1

    Sometimes a single drop of water is all Elly's cactuses need.

  4. 1000000

    1337

    123456

    424242

    13

    42

    Returns: 8484

  5. 8574

    77

    1000

    42

    71

    13

    Returns: 733

  6. 8574

    101

    1000

    42

    71

    13

    Returns: 541

  7. 5122656

    533

    100000

    1234567

    463

    179

    Returns: 95545

  8. 5122656

    1047

    100000

    1234567

    463

    179

    Returns: 49920

  9. 785646465

    8080

    1000000

    666666666

    34321981

    666421337

    Returns: 991200

  10. 785646465

    13333

    1000000

    666666666

    34321981

    666421337

    Returns: 516003

  11. 257020532

    2714

    932798

    1

    4461535

    1048576

    Returns: 932798

  12. 323999

    1

    324000

    1337

    80221

    14161

    Returns: 324000

  13. 999999

    42

    1000000

    0

    1

    1

    Returns: 999958

  14. 777776

    1

    999999

    0

    1

    2

    Returns: 777777

  15. 999999

    666

    1000000

    999999

    1

    999999

    Returns: 999334

  16. 999998

    1

    1000000

    999990

    1

    999997

    Returns: 999999

  17. 183966551

    183966550

    1

    61040464

    1135597

    131262535

    Returns: 1

  18. 131752571

    4254761

    1

    77374558

    18821797

    21627923

    Returns: -1

  19. 547914047

    455388442

    2

    92525604

    34244629

    25475623

    Returns: 2

  20. 519074051

    126751894

    2

    210120450

    74153437

    339840185

    Returns: -1

  21. 481342796

    264273521

    3

    217069274

    1725244

    85147657

    Returns: 2

  22. 140457299

    26244609

    3

    32441099

    28091461

    121593497

    Returns: -1

  23. 595387439

    595387438

    5

    45825434

    49615621

    221796451

    Returns: 1

  24. 933922383

    200176133

    5

    355650503

    233480597

    293746849

    Returns: -1

  25. 856191919

    530400209

    8

    325791709

    214047981

    302825323

    Returns: 2

  26. 696117851

    165128617

    8

    271187542

    232039285

    55695037

    Returns: -1

  27. 311415875

    181989817

    10

    4615422

    103805293

    90994909

    Returns: 6

  28. 485718974

    124651230

    10

    363375616

    32381266

    49910108

    Returns: -1

  29. 372213199

    50802950

    20

    282245400

    18610661

    125245591

    Returns: 20

  30. 163646511

    13512551

    20

    19903848

    40911629

    148519633

    Returns: -1

  31. 362649215

    45620593

    30

    266456523

    11332789

    28187249

    Returns: 25

  32. 933335702

    31105281

    30

    622576118

    34567990

    439820921

    Returns: -1

  33. 1742063

    419229

    50

    888512

    435517

    443659

    Returns: 13

  34. 857065949

    33811543

    50

    592711182

    57137731

    761905931

    Returns: -1

  35. 450493811

    31718779

    80

    429265451

    5561653

    125298125

    Returns: -1

  36. 115022239

    2555546

    80

    39403426

    14377781

    18846367

    Returns: -1

  37. 507037551

    220746443

    100

    138168463

    126759389

    498844469

    Returns: 6

  38. 936702583

    23108500

    100

    72176835

    24650069

    272459775

    Returns: -1

  39. 656614079

    20962157

    200

    163938875

    4559821

    294727891

    Returns: 168

  40. 348432515

    210378

    200

    303284945

    12904909

    258714529

    Returns: -1

  41. 557543599

    16160631

    300

    434797762

    27877181

    323648777

    Returns: 183

  42. 959340447

    2816202

    300

    601913200

    119917557

    219365083

    Returns: -1

  43. 895040351

    14934745

    500

    634920763

    37293349

    733185481

    Returns: 403

  44. 574393399

    2863782

    500

    207648428

    57439341

    180621093

    Returns: -1

  45. 395707760

    7590219

    800

    291290800

    1628428

    221871056

    Returns: 463

  46. 113732575

    40554

    800

    26089794

    14216573

    27768175

    Returns: -1

  47. 432668527

    2919297

    1000

    180871566

    108167133

    344243163

    Returns: 671

  48. 134688563

    51347

    1000

    110015537

    44896189

    76262683

    Returns: -1

  49. 994690314

    8902965

    2000

    110419186

    338216

    780379427

    Returns: 1035

  50. 614649631

    8174604

    2000

    148803089

    76831205

    55118503

    Returns: -1

  51. 407880683

    216704635

    3000

    146454270

    15106693

    151915921

    Returns: 3

  52. 487100843

    120595

    3000

    174057521

    54122317

    423909157

    Returns: -1

  53. 202715675

    77582755

    5000

    78368736

    22523965

    85614311

    Returns: 4

  54. 282391583

    167194

    5000

    52739370

    35298949

    38907539

    Returns: -1

  55. 835416559

    256818

    8000

    147134119

    208854141

    414289463

    Returns: 6109

  56. 52349663

    13410

    8000

    16805690

    6543709

    7379053

    Returns: -1

  57. 87038159

    61248

    10000

    79696111

    21759541

    83518373

    Returns: 2410

  58. 781045991

    23122

    10000

    2583273

    130174333

    487155973

    Returns: -1

  59. 507570074

    122282

    20000

    350003564

    33838006

    88778

    Returns: 15997

  60. 876612563

    120732

    20000

    172732300

    97401397

    358500115

    Returns: -1

  61. 259721747

    319079

    30000

    156468557

    28857973

    214000615

    Returns: 4009

  62. 776610415

    26123

    30000

    529736432

    194152605

    300706839

    Returns: -1

  63. 66516687

    2823421

    50000

    1929089

    16629173

    54497833

    Returns: 167

  64. 648098027

    37764

    50000

    523768897

    216032677

    342171295

    Returns: -1

  65. 226245967

    3085621

    80000

    220907015

    56561493

    37225707

    Returns: 354

  66. 126179855

    917

    80000

    33051301

    1168333

    81138665

    Returns: -1

  67. 420881231

    117289

    100000

    397023418

    105220309

    295277891

    Returns: 12764

  68. 78864411

    2257

    100000

    40838870

    651773

    68473947

    Returns: -1

  69. 525724687

    103174

    200000

    38902783

    131431173

    262158535

    Returns: 18113

  70. 518022935

    3049

    200000

    208983121

    86337157

    453445751

    Returns: -1

  71. 78218927

    11870

    300000

    68358175

    6518245

    1984637

    Returns: 20978

  72. 139372811

    1113

    300000

    57434141

    5161957

    58406473

    Returns: -1

  73. 875141231

    135442

    500000

    398965430

    218785309

    734666461

    Returns: 22412

  74. 742226655

    2844

    500000

    96690857

    92778333

    612281067

    Returns: -1

  75. 670919840

    256369

    800000

    279117301

    2760988

    625529527

    Returns: 21698

  76. 296954267

    15

    800000

    249610022

    15629173

    129548215

    Returns: -1

  77. 151808777

    114107

    1000000

    118858359

    4600267

    24765119

    Returns: 7638

  78. 350999247

    75

    1000000

    251921859

    87749813

    199507509

    Returns: -1

  79. 2

    1

    1

    0

    1

    1

    Returns: -1

  80. 2

    1

    2

    1

    2

    2

    Returns: 1

  81. 2

    1

    3

    1

    0

    0

    Returns: 1

  82. 71

    56

    5

    47

    62

    20

    Returns: 1

  83. 4

    3

    8

    0

    3

    4

    Returns: 3

  84. 2

    1

    10

    2

    2

    1

    Returns: -1

  85. 3

    1

    20

    2

    2

    0

    Returns: -1

  86. 3

    1

    30

    1

    3

    0

    Returns: -1

  87. 5

    2

    50

    1

    3

    0

    Returns: 2

  88. 47

    26

    80

    14

    36

    38

    Returns: -1

  89. 18

    5

    100

    17

    11

    7

    Returns: -1

  90. 4000

    3063

    200

    2636

    1472

    3557

    Returns: 1

  91. 166

    44

    300

    15

    81

    120

    Returns: 10

  92. 65

    63

    500

    40

    29

    21

    Returns: 1

  93. 365

    280

    800

    82

    340

    127

    Returns: 2

  94. 561

    251

    1000

    199

    160

    229

    Returns: 6

  95. 336

    200

    2000

    183

    74

    153

    Returns: 1

  96. 306

    8

    3000

    171

    177

    297

    Returns: -1

  97. 515

    164

    5000

    443

    479

    326

    Returns: -1

  98. 3846

    3794

    8000

    1767

    3478

    3801

    Returns: 1

  99. 2109

    1674

    10000

    1906

    1842

    1772

    Returns: 2

  100. 2551

    2383

    20000

    767

    1222

    528

    Returns: 1

  101. 3045

    1260

    30000

    514

    2161

    584

    Returns: 3

  102. 125000

    25732

    50000

    83162

    75032

    106816

    Returns: 31

  103. 8350

    3409

    80000

    2607

    404

    5360

    Returns: 3

  104. 80000

    51127

    100000

    53132

    27692

    62496

    Returns: 2

  105. 21231

    19047

    200000

    8914

    9849

    3181

    Returns: 1

  106. 6000000

    2360672

    300000

    4095428

    3103407

    4866712

    Returns: 6

  107. 65616

    5074

    500000

    59992

    32863

    53578

    Returns: 63

  108. 661157

    443675

    800000

    402527

    33170

    64614

    Returns: 1

  109. 473933

    223143

    1000000

    354858

    153135

    9747

    Returns: 6

  110. 1000000000

    30000

    1000000

    123123123

    123123123

    1000003

    Returns: 424220

  111. 1000000000

    1

    1000000

    0

    1

    2

    Returns: -1

  112. 8

    4

    1

    4

    2

    5

    Returns: 1

  113. 100

    1

    2

    1

    1

    99

    Returns: -1

  114. 1000000000

    100000000

    1000000

    3

    100000000

    100000000

    Returns: 56

  115. 1000000000

    5000

    1000000

    1

    1

    2000

    Returns: 499999

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: