Statistics

Problem Statement for "MuddyRoad2"

Problem Statement

Fox Ciel is going to walk along an unpaved road to her friend's house. For our purposes, the road can be considered a one-dimensional polyline consisting of N segments. The segments are numbered 0 through N-1 along the road. At the beginning, Ciel stands on the segment number 0. Her friend's house is on the segment number N-1.


Unfortunately, yesterday it rained, so some segments of the road are now muddy. Ciel has new shoes, so she must only use the other, dry segments. She knows that segments 0 and N-1 are dry. The friend just called her and gave her two additional pieces of information:

  • Out of the remaining N-2 segments, exactly muddyCount are muddy.
  • There is an even number of ways how Ciel can get to the friend's house without stepping into the mud, while making steps of length at most 2.

We will now explain the second information in more detail. When Ciel walks along the road, each of her steps has either length 1 or 2. A step of length 1 takes her from segment i to segment i+1. A step of length 2 takes her from segment i to segment i+2, skipping the (possibly, but not necessarily muddy) segment i+1.


Fox Ciel would like to use the information she has to determine how the road looks like. Of course, there may be multiple configurations that match the information. It is also possible that her friend was mistaken and there is no sequence of dry and muddy segments that matches what she told Ciel.


You are given the ints N and muddyCount. Count all the ways the road can look like, and return that count modulo 555,555,555.

Definition

Class:
MuddyRoad2
Method:
theCount
Parameters:
int, int
Returns:
int
Method signature:
int theCount(int N, int muddyCount)
(be sure your method is public)

Notes

  • Zero (0) is also an even number. Hence, if Ciel cannot reach her friend's house without stepping into the mud, there is an even number of ways to reach the house.
  • Two configurations of the road are different if some road segment is dry in one of them and muddy in the other.

Constraints

  • N will be between 2 and 555, inclusive.
  • muddyCount will be between 0 and N-2, inclusive.

Examples

  1. 5

    1

    Returns: 2

    There are two possible configurations of the road: .#... and ...#. (where '#' denotes a muddy segment and '.' a dry one).

  2. 5

    2

    Returns: 2

    Possible configurations: .##.. and ..##. Note that in these configurations, there are no ways to go from part 0 to part 4 without stepping onto any muddy parts. You have to count this kind of configurations too, since 0 is an even number.

  3. 10

    4

    Returns: 65

  4. 314

    78

    Returns: 498142902

  5. 555

    222

    Returns: 541606281

  6. 2

    0

    Returns: 0

  7. 3

    0

    Returns: 1

  8. 3

    1

    Returns: 0

  9. 4

    0

    Returns: 0

  10. 4

    1

    Returns: 0

  11. 4

    2

    Returns: 1

  12. 5

    0

    Returns: 0

  13. 5

    3

    Returns: 1

  14. 555

    0

    Returns: 1

  15. 555

    1

    Returns: 368

  16. 555

    2

    Returns: 101568

  17. 555

    553

    Returns: 1

  18. 555

    552

    Returns: 553

  19. 555

    551

    Returns: 152628

  20. 551

    44

    Returns: 370263114

  21. 550

    32

    Returns: 191831629

  22. 552

    408

    Returns: 367514370

  23. 550

    155

    Returns: 206394093

  24. 552

    490

    Returns: 79384035

  25. 550

    100

    Returns: 214249245

  26. 553

    449

    Returns: 189651465

  27. 552

    28

    Returns: 388963015

  28. 555

    79

    Returns: 275324190

  29. 555

    497

    Returns: 121006185

  30. 551

    300

    Returns: 433110435

  31. 553

    481

    Returns: 148498515

  32. 552

    404

    Returns: 469165365

  33. 554

    145

    Returns: 260141345

  34. 553

    155

    Returns: 438163677

  35. 555

    130

    Returns: 263039908

  36. 555

    248

    Returns: 257269323

  37. 551

    133

    Returns: 97420847

  38. 552

    504

    Returns: 258794445

  39. 555

    179

    Returns: 398531700

  40. 185

    45

    Returns: 76442085

  41. 263

    85

    Returns: 496249136

  42. 11

    0

    Returns: 0

  43. 431

    426

    Returns: 13067054

  44. 313

    18

    Returns: 449909475

  45. 389

    179

    Returns: 96532467

  46. 190

    104

    Returns: 182989420

  47. 420

    103

    Returns: 476477145

  48. 210

    73

    Returns: 376235647

  49. 427

    273

    Returns: 228160755

  50. 202

    137

    Returns: 267944565

  51. 165

    59

    Returns: 40455450

  52. 190

    65

    Returns: 202196919

  53. 26

    15

    Returns: 1307504

  54. 536

    374

    Returns: 216998280

  55. 89

    19

    Returns: 236601030

  56. 438

    311

    Returns: 488030553

  57. 123

    96

    Returns: 472504689

  58. 500

    4

    Returns: 522246270

  59. 468

    2

    Returns: 72075

  60. 551

    537

    Returns: 33869106

  61. 254

    216

    Returns: 55183095

  62. 58

    6

    Returns: 30867648

  63. 293

    207

    Returns: 201267795

  64. 481

    8

    Returns: 553652025

  65. 16

    3

    Returns: 304

  66. 307

    32

    Returns: 205435426

  67. 165

    124

    Returns: 168511185

  68. 451

    17

    Returns: 534049564

  69. 360

    203

    Returns: 222879393

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: