Statistics

Problem Statement for "NoDistanceD"

Problem Statement

Little Maurice has a bag with N balls, numbered from 1 to N.

He draws the balls from the bag, one at a time.

He stops immediately after he removes a ball that differs from any of the previously removed balls by exactly D. If that never happens, he also stops after drawing the last ball from the bag.

Calculate and return the largest possible number of balls Maurice might remove from the bag during the activity described above.

Definition

Class:
NoDistanceD
Method:
count
Parameters:
long, long
Returns:
long
Method signature:
long count(long N, long D)
(be sure your method is public)

Constraints

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

Examples

  1. 5

    1

    Returns: 4

    As D=1, Maurice stops as soon as he sees two balls with consecutive numbers. Sometimes the process will end right after the second ball is drawn, e.g., if he draws 3 followed by 4, or if he draws 3 followed by 2. Sometimes the process ends after the third ball, e.g., if he draws the balls in order 1, 4, 3. The longest the process can take is four balls. For example, Maurice could draw the balls in the order 1, 5, 3, 4.

  2. 5

    2

    Returns: 4

    Again, the maximum number of balls Maurice can draw is four. This time some valid orders in which he can draw four balls include 1, 5, 4, 3 and 2, 1, 5, 4.

  3. 123456789012

    234567890123

    Returns: 123456789012

    As no two balls in Maurice's bag differ by 234567890123, he will keep on drawing until he empties the whole bag.

  4. 123456789012

    123456789012

    Returns: 123456789012

  5. 123456789012

    123456789011

    Returns: 123456789012

  6. 123456789012

    123456789010

    Returns: 123456789011

  7. 1

    7

    Returns: 1

  8. 2

    1

    Returns: 2

  9. 2

    2

    Returns: 2

  10. 3

    1

    Returns: 3

  11. 3

    2

    Returns: 3

  12. 4

    1

    Returns: 3

  13. 4

    2

    Returns: 3

  14. 4

    3

    Returns: 4

  15. 5

    1

    Returns: 4

  16. 5

    2

    Returns: 4

  17. 5

    3

    Returns: 4

  18. 5

    4

    Returns: 5

  19. 6

    1

    Returns: 4

  20. 6

    2

    Returns: 5

  21. 6

    3

    Returns: 4

  22. 6

    4

    Returns: 5

  23. 6

    5

    Returns: 6

  24. 12

    3

    Returns: 7

  25. 234567890123

    1

    Returns: 117283945063

  26. 234567890123

    2

    Returns: 117283945063

  27. 234567890123

    3

    Returns: 117283945063

  28. 234567890123

    1245456

    Returns: 117284544060

  29. 234567890123

    12653266623

    Returns: 120688490517

  30. 4718803

    255999072

    Returns: 4718803

  31. 104554406420

    5955217264

    Returns: 53596955377

  32. 550195858414

    128654

    Returns: 275097969257

  33. 23311791531

    56300

    Returns: 11655901601

  34. 398384431

    6

    Returns: 199192219

  35. 7062484

    48086382200

    Returns: 7062484

  36. 2507971

    14823990

    Returns: 2507971

  37. 5380883297

    27356

    Returns: 2690448054

  38. 15909

    234

    Returns: 7957

  39. 433243449084

    49911

    Returns: 216621725761

  40. 4530769

    4436275

    Returns: 4436276

  41. 390160982005

    390127917509

    Returns: 390127917510

  42. 85092

    83899

    Returns: 83900

  43. 24

    18

    Returns: 19

  44. 391885784965

    391877969824

    Returns: 391877969825

  45. 2771

    2465

    Returns: 2466

  46. 432

    431

    Returns: 432

  47. 76123533

    67387275

    Returns: 67387276

  48. 71002

    70654

    Returns: 70655

  49. 7883720804

    7883712656

    Returns: 7883712657

  50. 11026628440

    21

    Returns: 5513314229

  51. 858

    5

    Returns: 431

  52. 14

    12

    Returns: 13

  53. 42677

    3

    Returns: 21340

  54. 81459717906

    519151

    Returns: 40729991706

  55. 5347748357

    2797255

    Returns: 2674175781

  56. 561131087

    6

    Returns: 280565545

  57. 32137878921

    19

    Returns: 16068939465

  58. 15457231292

    9690

    Returns: 7728618031

  59. 103

    75

    Returns: 76

  60. 9231579

    4668061

    Returns: 4668062

  61. 51533808

    93141

    Returns: 25800058

  62. 371828

    1003

    Returns: 186274

  63. 257000819

    102

    Returns: 128500417

  64. 171

    1

    Returns: 87

  65. 28

    1

    Returns: 15

  66. 4102225513

    10443553

    Returns: 2055289126

  67. 6015027351

    58

    Returns: 3007513680

  68. 81102786

    55525680

    Returns: 55525681

  69. 187003764

    1881390

    Returns: 94069501

  70. 20

    5

    Returns: 11

  71. 42830565591

    1948185

    Returns: 21416116072

  72. 6180981859

    132964135

    Returns: 3122806755

  73. 1151487

    120

    Returns: 575761

  74. 163741473429

    3930714

    Returns: 81872562238

  75. 13

    12

    Returns: 13

  76. 110712

    5857

    Returns: 58000

  77. 14607666

    359

    Returns: 7303856

  78. 286978148

    838425

    Returns: 143607474

  79. 81979605

    8369982

    Returns: 41849911

  80. 71486

    25250

    Returns: 46237

  81. 37478609

    3

    Returns: 18739306

  82. 7514

    31

    Returns: 3764

  83. 147942

    1443

    Returns: 74350

  84. 30215

    131

    Returns: 15151

  85. 93454

    13638

    Returns: 52541

  86. 36127049

    3

    Returns: 18063526

  87. 11

    2

    Returns: 7

  88. 86721349926

    39611640442

    Returns: 47109709485

  89. 245957608

    168464850

    Returns: 168464851

  90. 896

    17

    Returns: 455

  91. 155169726072

    2

    Returns: 77584863037

  92. 160

    1

    Returns: 81

  93. 4250454186

    113210308

    Returns: 2150995853

  94. 13453473

    937922

    Returns: 6888020

  95. 17970303

    77

    Returns: 8985174

  96. 236369003254

    2715780

    Returns: 118185314041

  97. 5536424

    1357943

    Returns: 2820539

  98. 198221

    180

    Returns: 99181

  99. 2992

    881

    Returns: 1763

  100. 11

    3

    Returns: 7

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: