Statistics

Problem Statement for "AppleTrees"

Problem Statement

Rabbit Hanako likes apples. She decided to plant apple trees along a straight road.

The road has D candidate positions for planting apple trees. These positions are numbered 0 through D-1, from left to right. The distance between position x and position y is |x-y| meters (|x-y| denotes the absolute value of x-y). She wants to plant N apple trees numbered from 0 to N-1 in different positions. The trees may be planted in any order. The i-th tree won't grow if there are other trees which are closer than r[i] meters. In other words, if i and j are distinct, the distance between the i-th tree and the j-th tree must be at least max(r[i],r[j]) meters.

Return the number of ways to plant all apple trees modulo 1,000,000,007.

Definition

Class:
AppleTrees
Method:
theCount
Parameters:
int, int[]
Returns:
int
Method signature:
int theCount(int D, int[] r)
(be sure your method is public)

Constraints

  • D will be between 1 and 100,000, inclusive.
  • r will contain between 1 and 40 elements, inclusive.
  • Each element of r will be between 1 and 40, inclusive.

Examples

  1. 10

    {40}

    Returns: 10

    There are 10 candidate positions for the only tree.

  2. 4

    {1, 1, 1, 1}

    Returns: 24

    Trees must be planted in different positions, so the number of ways to plant all trees is 4! = 24.

  3. 4

    {1, 1, 2}

    Returns: 4

    The following 4 ways are possible: Plant the 0th tree in position 0, the 1st tree in position 1, and the 2nd tree in position 3. Plant the 0th tree in position 1, the 1st tree in position 0, and the 2nd tree in position 3. Plant the 0th tree in position 2, the 1st tree in position 3, and the 2nd tree in position 0. Plant the 0th tree in position 3, the 1st tree in position 2, and the 2nd tree in position 0.

  4. 58

    {5, 8}

    Returns: 2550

  5. 47

    {4, 8, 9}

    Returns: 28830

  6. 100000

    {21, 37, 23, 13, 32, 22, 9, 39}

    Returns: 923016564

  7. 100000

    {40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40}

    Returns: 24331430

  8. 100000

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40}

    Returns: 714711938

  9. 100000

    {8, 27, 12, 9, 33, 38, 10, 28, 4, 2, 30, 40, 2, 17, 32, 24, 25, 13, 26, 21, 25, 25, 35, 13, 30, 18, 6, 38, 12, 20, 23, 24, 15, 6, 10, 32, 28, 7, 24, 19}

    Returns: 218519605

  10. 100000

    {7, 37, 16, 21, 38, 25, 34, 22, 36, 16, 11, 22, 26, 17, 26, 34, 20, 21, 23, 15, 32, 33, 30, 1, 27, 20, 23, 15, 16, 1, 3, 9, 29, 7, 21, 1, 28, 32, 27, 3}

    Returns: 407032791

  11. 100000

    {13, 13, 19, 12, 26, 22, 30, 22, 17, 35, 1, 8, 22, 35, 24, 10, 7, 32, 28, 28, 40, 2, 28, 25, 10, 32, 26, 39, 37, 11, 38, 15, 21, 23, 8, 28, 9, 30, 11, 7}

    Returns: 848904165

  12. 100000

    {20, 26, 26, 37, 14, 36, 40, 12, 17, 12, 14, 1, 33, 35, 11, 27, 21, 33, 34, 21, 22, 16, 16, 38, 6, 6, 39, 14, 1, 26, 31, 20, 11, 30, 6, 39, 33, 26, 10, 11}

    Returns: 500775678

  13. 100000

    {29, 10, 9, 4, 38, 32, 6, 38, 11, 6, 33, 13, 26, 25, 21, 39, 10, 27, 31, 10, 6, 11, 3, 4, 17, 8, 9, 16, 7, 24, 39, 22, 12, 35, 20, 40, 21, 3, 40, 39}

    Returns: 303932276

  14. 100000

    {28, 15, 15, 15, 12, 38, 24, 4, 10, 29, 37, 34, 19, 2, 13, 3, 40, 35, 1, 15, 15, 34, 25, 27, 27, 16, 8, 26, 15, 21, 37, 7, 34, 8, 25, 35, 32, 29, 37, 7}

    Returns: 475613033

  15. 100000

    {25, 1, 2, 34, 40, 26, 9, 15, 20, 28, 8, 18, 4, 5, 30, 18, 18, 14, 20, 18, 5, 3, 27, 2, 35, 32, 32, 35, 6, 37, 28, 37, 36, 15, 2, 37, 24, 4, 12, 31}

    Returns: 467164612

  16. 100000

    {16, 21, 23, 23, 2, 15, 19, 13, 22, 2, 5, 25, 30, 27, 3, 20, 39, 6, 17, 11, 4, 1, 3, 2, 35, 6, 8, 13, 8, 17, 18, 11, 24, 36, 10, 40, 37, 21, 22, 34}

    Returns: 556856111

  17. 100000

    {34, 10, 3, 34, 37, 10, 37, 38, 1, 39, 17, 8, 6, 34, 30, 31, 14, 30, 22, 11, 19, 14, 5, 23, 36, 12, 37, 36, 11, 33, 22, 29, 38, 36, 32, 6, 16, 38, 15, 38}

    Returns: 169047545

  18. 100000

    {14, 36, 14, 35, 28, 30, 30, 3, 28, 27, 35, 16, 10, 40, 13, 25, 11, 5, 27, 15, 22, 23, 18, 37, 10, 31, 21, 2, 20, 11, 30, 12, 20, 9, 15, 36, 32, 38, 3, 21}

    Returns: 273170335

  19. 78368

    {6, 40, 5, 18, 13, 15, 2, 36, 9, 24, 33, 2, 39, 35, 1, 5, 12, 31, 21, 13, 5, 29, 39, 39, 16, 8, 16, 35, 22, 13, 34, 32, 22, 29, 31, 38, 29, 20, 10, 6}

    Returns: 950014493

  20. 61572

    {37, 26, 23, 28, 5, 39, 21, 23, 8, 9, 36, 28, 33, 22, 38, 37, 23, 18, 37, 7, 12, 40, 27, 27, 10, 10, 36, 6, 34, 20, 13, 21, 17, 24, 27, 22, 24, 17, 34, 8}

    Returns: 620297046

  21. 10643

    {34, 26, 38, 37, 3, 12, 29, 7, 13, 31, 1, 17, 39, 4, 33, 34, 13, 14, 34, 23, 40, 20, 29, 9, 40, 17, 29, 29, 35, 38, 33, 1, 4, 25, 14, 33, 27, 36, 13, 32}

    Returns: 559510586

  22. 91691

    {30, 21, 40, 7, 12, 15, 11, 21, 30, 38, 23, 7, 28, 25, 21, 23, 15, 36, 30, 13, 27, 27, 26, 3, 2, 32, 5, 17, 15, 9, 28, 24, 14, 8, 19, 3, 40, 30, 28, 7}

    Returns: 11981090

  23. 7613

    {2, 38, 24, 10, 13, 18, 29, 8, 31, 5, 2, 23, 10, 17, 14, 2, 16, 2, 17, 32, 7, 9, 23, 9, 29, 2, 32, 2, 21, 1, 17, 22, 33, 1, 32, 29, 4, 39, 18, 23}

    Returns: 472755403

  24. 50808

    {31, 18, 36, 19, 17, 7, 40, 15, 39, 9, 18, 31, 32, 32, 36, 28, 3, 25, 5, 9, 18, 20, 4, 38, 37, 8, 35, 15, 16, 23, 36, 3, 21, 1, 15, 6, 30, 7, 2, 10}

    Returns: 104316779

  25. 67448

    {17, 26, 14, 33, 18, 22, 39, 10, 27, 15, 8, 35, 6, 3, 21, 25, 16, 9, 15, 37, 3, 38, 36, 5, 35, 34, 20, 31, 17, 15, 33, 1, 3, 29, 4, 30, 10, 13, 21, 37}

    Returns: 687159416

  26. 31016

    {2, 3, 40, 21, 35, 11, 38, 8, 40, 7, 33, 21, 6, 40, 34, 3, 30, 25, 18, 6, 6, 18, 8, 38, 24, 39, 10, 38, 22, 8, 38, 18, 23, 25, 17, 9, 18, 27, 35, 23}

    Returns: 474911888

  27. 43211

    {33, 20, 27, 21, 9, 36, 8, 23, 27, 10, 9, 20, 18, 31, 36, 30, 25, 31, 37, 10, 18, 20, 30, 14, 31, 4, 21, 10, 32, 29, 27, 11, 10, 23, 39, 3, 30, 4, 4, 34}

    Returns: 258238152

  28. 13031

    {28, 31, 28, 33, 8, 35, 19, 35, 12, 13, 9, 7, 14, 2, 19, 12, 19, 7, 16, 35, 27, 31, 25, 10, 36, 38, 14, 40, 22, 1, 3, 19, 26, 39, 1, 8, 26, 24, 11, 21}

    Returns: 923431277

  29. 100000

    {32, 33, 36, 39, 31, 36, 40, 31, 37, 40, 36, 35, 31, 35, 39, 33, 33, 40, 37, 31, 32, 33, 34, 32, 31, 33, 37, 34, 39, 35, 37, 38, 38, 39, 36, 38, 35, 40, 36, 36}

    Returns: 674882745

  30. 100000

    {37, 37, 35, 40, 37, 31, 38, 40, 37, 34, 31, 34, 36, 38, 33, 37, 33, 40, 36, 31, 40, 37, 38, 40, 34, 31, 31, 35, 31, 37, 36, 40, 31, 38, 35, 33, 33, 37, 39, 33}

    Returns: 787805446

  31. 100000

    {31, 36, 34, 35, 35, 36, 31, 38, 37, 37, 33, 40, 36, 36, 36, 39, 35, 34, 36, 32, 33, 35, 31, 35, 40, 38, 37, 33, 33, 39, 35, 34, 35, 31, 33, 35, 34, 33, 32, 40}

    Returns: 11104825

  32. 100000

    {39, 33, 38, 33, 33, 31, 34, 34, 34, 33, 31, 33, 37, 36, 34, 33, 33, 39, 36, 38, 31, 34, 36, 38, 35, 36, 34, 38, 34, 33, 33, 40, 36, 36, 36, 37, 34, 34, 34, 38}

    Returns: 969369096

  33. 100000

    {36, 39, 33, 40, 39, 33, 40, 37, 35, 31, 34, 31, 31, 37, 35, 36, 33, 40, 32, 35, 33, 32, 33, 32, 40, 33, 34, 38, 39, 31, 37, 37, 34, 34, 32, 36, 38, 35, 36, 32}

    Returns: 105350535

  34. 897

    {14, 21, 8, 1, 13, 33, 9, 5, 36, 24, 14, 4, 32, 4, 26, 40, 22, 10, 23, 18, 19, 9, 17, 33, 11, 5, 35, 26, 23, 1, 8, 10, 21, 14, 18, 14, 9, 24, 14, 27}

    Returns: 169905204

  35. 1052

    {26, 28, 15, 12, 2, 39, 31, 26, 24, 5, 9, 5, 17, 35, 4, 8, 37, 19, 17, 28, 19, 24, 13, 11, 35, 19, 29, 7, 38, 32, 8, 5, 34, 34, 14, 33, 21, 33, 39, 12}

    Returns: 60826073

  36. 1107

    {35, 38, 9, 36, 12, 35, 15, 24, 33, 26, 6, 1, 37, 3, 24, 27, 33, 36, 26, 1, 32, 12, 38, 29, 4, 19, 31, 8, 10, 36, 3, 3, 36, 24, 18, 39, 7, 26, 28, 16}

    Returns: 809382457

  37. 1082

    {21, 17, 29, 1, 34, 1, 25, 8, 19, 11, 27, 33, 37, 20, 1, 2, 11, 21, 32, 37, 24, 30, 25, 29, 28, 4, 11, 27, 29, 34, 17, 31, 19, 4, 30, 8, 3, 18, 11, 38}

    Returns: 516588995

  38. 906

    {29, 25, 18, 33, 29, 22, 18, 33, 7, 9, 13, 38, 9, 27, 28, 19, 2, 5, 18, 13, 19, 34, 1, 32, 6, 5, 28, 16, 15, 22, 3, 7, 4, 31, 37, 16, 4, 10, 7, 3}

    Returns: 525897281

  39. 1041

    {21, 21, 40, 32, 10, 11, 14, 29, 2, 12, 2, 40, 35, 17, 18, 31, 37, 9, 4, 34, 6, 4, 16, 3, 18, 19, 7, 27, 5, 38, 15, 36, 9, 28, 16, 28, 15, 14, 27, 40}

    Returns: 724118712

  40. 1040

    {37, 23, 22, 9, 6, 2, 6, 18, 32, 34, 39, 19, 4, 25, 11, 39, 30, 24, 11, 17, 16, 5, 26, 1, 29, 38, 13, 29, 36, 24, 31, 6, 15, 27, 18, 25, 12, 29, 28, 1}

    Returns: 105692396

  41. 1060

    {39, 40, 7, 5, 28, 31, 32, 1, 32, 34, 2, 6, 21, 7, 38, 7, 28, 10, 36, 9, 20, 5, 36, 14, 34, 15, 3, 13, 9, 40, 13, 7, 12, 21, 23, 1, 17, 1, 22, 38}

    Returns: 828406613

  42. 1104

    {35, 18, 8, 15, 40, 17, 38, 16, 19, 20, 1, 35, 15, 6, 8, 27, 28, 33, 35, 6, 28, 17, 29, 29, 25, 39, 3, 31, 6, 23, 12, 20, 18, 39, 23, 35, 22, 21, 27, 5}

    Returns: 400387332

  43. 1129

    {36, 1, 8, 13, 21, 37, 21, 37, 36, 10, 19, 37, 17, 38, 15, 27, 38, 39, 30, 39, 27, 23, 33, 14, 19, 15, 36, 1, 10, 27, 31, 15, 22, 26, 10, 1, 40, 22, 8, 18}

    Returns: 343828589

  44. 1

    {20}

    Returns: 1

  45. 11

    {11, 7}

    Returns: 0

  46. 72

    {36, 22, 3}

    Returns: 2240

  47. 71

    {8, 27, 22, 15}

    Returns: 1700

  48. 137

    {15, 39, 7, 40, 19}

    Returns: 2693732

  49. 154

    {1, 27, 38, 27, 31, 2}

    Returns: 110506944

  50. 195

    {20, 15, 29, 32, 37, 22, 38}

    Returns: 34611592

  51. 259

    {38, 24, 39, 23, 37, 27, 29, 39}

    Returns: 830755385

  52. 209

    {8, 1, 12, 40, 19, 2, 20, 12, 33}

    Returns: 257583360

  53. 152

    {15, 38, 26, 13, 6, 11, 3, 13, 15, 5}

    Returns: 231996288

  54. 1558

    {40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40}

    Returns: 0

  55. 1559

    {40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40}

    Returns: 0

  56. 1560

    {40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40}

    Returns: 0

  57. 1561

    {40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40}

    Returns: 799434881

  58. 1562

    {40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40}

    Returns: 776829897

  59. 12489

    {35}

    Returns: 12489

  60. 32298

    {2}

    Returns: 32298

  61. 75495

    {17}

    Returns: 75495

  62. 81800

    {19}

    Returns: 81800

  63. 85355

    {9}

    Returns: 85355

  64. 790

    {19, 7, 4, 38, 3, 31, 9, 3, 25, 4, 40, 36, 14, 16, 38, 5, 2, 5, 31, 23, 35, 28, 33, 11, 1, 39, 24, 33, 34, 33, 28, 24, 4, 18, 18, 1, 27, 21, 20, 7}

    Returns: 0

  65. 866

    {35, 6, 5, 33, 22, 40, 18, 37, 39, 15, 12, 15, 36, 30, 4, 28, 21, 15, 36, 39, 1, 11, 3, 5, 19, 33, 33, 12, 28, 39, 1, 35, 22, 25, 13, 15, 36, 19, 12, 20}

    Returns: 0

  66. 791

    {34, 1, 22, 37, 20, 34, 1, 16, 7, 26, 31, 9, 11, 21, 20, 25, 8, 15, 31, 14, 2, 35, 29, 1, 36, 16, 21, 31, 34, 33, 15, 27, 38, 28, 10, 7, 26, 6, 11, 4}

    Returns: 0

  67. 729

    {18, 15, 10, 11, 24, 2, 10, 35, 2, 24, 12, 39, 11, 33, 19, 3, 8, 2, 34, 18, 8, 22, 13, 24, 30, 33, 27, 9, 6, 5, 15, 28, 20, 20, 24, 4, 38, 39, 2, 35}

    Returns: 0

  68. 759

    {10, 2, 5, 19, 27, 6, 2, 33, 40, 21, 3, 7, 3, 33, 39, 17, 28, 2, 34, 14, 1, 36, 16, 24, 26, 40, 27, 11, 34, 3, 33, 11, 11, 26, 11, 12, 5, 20, 29, 40}

    Returns: 0

  69. 10

    {40 }

    Returns: 10

  70. 100000

    {5, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40 }

    Returns: 714711938

  71. 100000

    {2, 28, 15, 21, 10, 5, 39, 39, 3, 25, 26, 26, 2, 28, 2, 12, 36, 23, 28, 37, 32, 5, 23, 34, 13, 23, 22, 37, 39, 16, 8, 7, 12, 19, 30, 33, 28, 20, 36, 15 }

    Returns: 993035722

  72. 99997

    {11, 17, 24, 10, 19, 14, 28, 28, 12, 14, 15, 15, 11, 17, 11, 21, 25, 12, 17, 26, 21, 14, 12, 23, 22, 12, 11, 26, 28, 25, 17, 16, 21, 28, 19, 22, 17, 29, 25, 24 }

    Returns: 996441691

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: