Statistics

Problem Statement for "JumpFurther"

Problem Statement

Little Fox Jiro is standing at the bottom of a long flight of stairs. The bottom of the stairs has number 0, the bottommost step has number 1, the next step has number 2, and so on. The staircase is so long that Jiro is guaranteed not to reach its top.

Jiro will now perform N consecutive actions. The actions are numbered 1 through N, in order. When performing action X, Jiro chooses between two options: either he does nothing, or he jumps exactly X steps up the stairs. In other words, if Jiro starts performing action X standing on step Y, he will end it either on step Y, or on step Y+X.

For example, if N=3, Jiro will make three consecutive choices: whether or not to jump 1 step upwards, 2 steps upwards, and then 3 steps upwards.

One of the steps is broken. The number of this step is badStep. Jiro cannot jump onto this step.

You are given the ints N and badStep. Compute and return the number of the topmost step that can be reached by Jiro.

Definition

Class:
JumpFurther
Method:
furthest
Parameters:
int, int
Returns:
int
Method signature:
int furthest(int N, int badStep)
(be sure your method is public)

Constraints

  • N will be between 1 and 2,000, inclusive.
  • badStep will be between 1 and 4,000,000, inclusive.

Examples

  1. 2

    2

    Returns: 3

    The optimal strategy is to jump upwards twice: from step 0 to step 1, and then from step 1 to step 3. This trajectory avoids the broken step.

  2. 2

    1

    Returns: 2

    In this case step 1 is broken, so Jiro cannot jump upwards as his first action. The optimal strategy is to first stay on step 0, and then to jump from step 0 to step 2.

  3. 3

    3

    Returns: 5

  4. 1313

    5858

    Returns: 862641

  5. 1

    757065

    Returns: 1

  6. 2000

    4000000

    Returns: 2001000

  7. 2000

    1

    Returns: 2000999

  8. 1

    1

    Returns: 0

  9. 2000

    2001000

    Returns: 2000999

  10. 1

    1

    Returns: 0

  11. 2

    2

    Returns: 3

  12. 3

    2

    Returns: 6

  13. 4

    3

    Returns: 9

  14. 5

    1

    Returns: 14

  15. 13

    4

    Returns: 91

  16. 22

    12

    Returns: 253

  17. 31

    2

    Returns: 496

  18. 40

    10

    Returns: 819

  19. 49

    15

    Returns: 1224

  20. 2000

    1888

    Returns: 2001000

  21. 1993

    219

    Returns: 1987021

  22. 1986

    257

    Returns: 1973091

  23. 1979

    65

    Returns: 1959210

  24. 1972

    717

    Returns: 1945378

  25. 1965

    1376

    Returns: 1931595

  26. 17

    55

    Returns: 152

  27. 25

    1

    Returns: 324

  28. 33

    28

    Returns: 560

  29. 41

    105

    Returns: 860

  30. 49

    45

    Returns: 1224

  31. 2000

    199396

    Returns: 2000999

  32. 1987

    7875

    Returns: 1975077

  33. 1974

    355746

    Returns: 1949324

  34. 1961

    305371

    Returns: 1923740

  35. 1948

    65341

    Returns: 1898325

  36. 1935

    41616

    Returns: 1873079

  37. 1499

    1122751

    Returns: 1124249

  38. 1599

    1268028

    Returns: 1279199

  39. 1699

    1430586

    Returns: 1444149

  40. 1799

    1601155

    Returns: 1619099

  41. 1899

    1794565

    Returns: 1804049

  42. 1999

    1983036

    Returns: 1998999

  43. 2000

    287332

    Returns: 2001000

  44. 1699

    1827096

    Returns: 1444150

  45. 1398

    2120892

    Returns: 977901

  46. 1097

    3205588

    Returns: 602253

  47. 796

    3444833

    Returns: 317206

  48. 495

    2230356

    Returns: 122760

  49. 2

    3

    Returns: 2

  50. 20

    21

    Returns: 209

  51. 5

    10

    Returns: 14

  52. 3

    6

    Returns: 5

  53. 2000

    400000

    Returns: 2001000

  54. 4

    6

    Returns: 9

  55. 5

    15

    Returns: 14

  56. 7

    15

    Returns: 27

  57. 1989

    3999999

    Returns: 1979055

  58. 1

    100

    Returns: 1

  59. 10

    55

    Returns: 54

  60. 3

    10

    Returns: 6

  61. 14

    55

    Returns: 104

  62. 5

    6

    Returns: 14

  63. 15

    15

    Returns: 119

  64. 5

    3

    Returns: 14

  65. 2000

    3545

    Returns: 2001000

  66. 4

    10

    Returns: 9

  67. 100

    7

    Returns: 5050

  68. 10

    15

    Returns: 54

  69. 5

    7

    Returns: 15

  70. 1

    6

    Returns: 1

  71. 5

    21

    Returns: 15

  72. 1999

    1999000

    Returns: 1998999

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: