Statistics

Problem Statement for "TreePlanting"

Problem Statement

A farmer wants to plant a row of trees along the front of his house. He has two different kinds of trees, some which are plain looking, and other, more expensive, fancy trees. He wishes to plant the trees in such a way that not all of the fancy trees are grouped together, so he insists that no two fancy trees be adjacent to one another.

You are given an int total indicating the total number of trees to be planted, and an int fancy which is the number of fancy trees. You are to return a long indicating the number of possible tree arrangements that meet the farmer's criteria of having no two fancy trees adjacent to one another.

Definition

Class:
TreePlanting
Method:
countArrangements
Parameters:
int, int
Returns:
long
Method signature:
long countArrangements(int total, int fancy)
(be sure your method is public)

Notes

  • You may assume that each fancy tree is identical to one other, and likewise for the plain trees.
  • If no valid arrangements are possible, the return value should be 0.

Constraints

  • total will be between 1 and 60, inclusive.
  • fancy will be between 1 and 60, inclusive.
  • fancy will be less than or equal to total.

Examples

  1. 4

    2

    Returns: 3

    Here, we have two plain trees, and two fancy trees. There are only three acceptable arrangements: PFPF, FPPF or FPFP. Any other arrangement would have two fancy trees next to each other.

  2. 3

    1

    Returns: 3

    There is only one fancy tree, and it can go in any of three locations.

  3. 4

    3

    Returns: 0

    There is no way to place all three fancy trees without two of them being next to each other.

  4. 10

    4

    Returns: 35

  5. 60

    17

    Returns: 686353797976

  6. 55

    20

    Returns: 7307872110

  7. 41

    19

    Returns: 8855

  8. 10

    3

    Returns: 56

  9. 55

    35

    Returns: 0

  10. 19

    17

    Returns: 0

  11. 58

    21

    Returns: 28781143380

  12. 45

    20

    Returns: 230230

  13. 36

    12

    Returns: 5200300

  14. 22

    5

    Returns: 8568

  15. 58

    12

    Returns: 52251400851

  16. 60

    60

    Returns: 0

  17. 60

    59

    Returns: 0

  18. 60

    31

    Returns: 0

  19. 60

    30

    Returns: 31

  20. 1

    1

    Returns: 1

  21. 2

    2

    Returns: 0

  22. 60

    15

    Returns: 511738760544

  23. 60

    10

    Returns: 12777711870

  24. 60

    20

    Returns: 269128937220

  25. 60

    29

    Returns: 4960

  26. 60

    30

    Returns: 31

  27. 60

    22

    Returns: 51021117810

  28. 3

    2

    Returns: 1

  29. 51

    15

    Returns: 9364199760

  30. 60

    17

    Returns: 686353797976

  31. 60

    12

    Returns: 92263734836

  32. 10

    4

    Returns: 35

  33. 59

    20

    Returns: 137846528820

  34. 60

    25

    Returns: 600805296

  35. 60

    18

    Returns: 608359048206

  36. 5

    3

    Returns: 1

  37. 9

    5

    Returns: 1

  38. 18

    1

    Returns: 18

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: