Statistics

Problem Statement for "TheCards"

Problem Statement

John is playing a solitaire computer game. There are n cards numbered from 1 to n and m slots numbered form 1 to m from the left to the right. He has to place each card into some slot using the following rules.

Basic rules:

  • The first card (card number 1) may be placed in any slot.
  • The second card (card number 2) must be placed exactly dist[0] slots to the left or exactly dist[0] slots to the right of the first card.
  • Similarly, each card number i (i > 1) must be placed exactly dist[i-2] slots to the left or exactly dist[i-2] slots to the right of the previous card (card number i-1).
  • Finally, if the last card (card number n) is exactly dist[n-1] slots to the left or exactly dist[n-1] slots to the right of the first card (card number 1) then John wins the game.

Special cases:

  • If an element of dist is equal to 0, then the corresponding card should be placed into the same slot as previous card.
  • If an element of dist is equal to -1, then the distance between the corresponding card and the previous card can be arbitrary.

You are given int[] dist that contains exactly n elements and the int m. Return the number (modulo 1234567891) of ways to place the cards into the slots so that John wins.

Definition

Class:
TheCards
Method:
find
Parameters:
int[], int
Returns:
int
Method signature:
int find(int[] dist, int m)
(be sure your method is public)

Notes

  • More than one card can be placed into a single slot.
  • Slots do not wrap. There are no slots to the left of slot number 1 and no slots to the right of slot number m.

Constraints

  • dist will contain between 2 and 36 elements, inclusive.
  • Each element of dist will be between -1 and 10,000, inclusive.
  • m will be between 1 and 1,000,000, inclusive.

Examples

  1. {3, 1, 2, 1, 1}

    5

    Returns: 8

    Several possible solutions are shown below (in order from card 1 to card 5): slot 1, slot 4, slot 5, slot 3, slot 2; slot 1, slot 4, slot 3, slot 1, slot 2; slot 2, slot 5, slot 4, slot 2, slot 1; ...

  2. {4, 7}

    47

    Returns: 0

    There is no way to win for John in this case.

  3. {1, 1, 1, 1}

    7

    Returns: 32

  4. {5, -1, -1, 4, 0, 2, -1, 8, 1, 2}

    11

    Returns: 4224

  5. {1, 2, 3, 4, 10}

    11

    Returns: 2

  6. {1, 2, 3, 4, 10}

    100

    Returns: 180

  7. {1, 1}

    2

    Returns: 2

  8. {7, 8, 9, 2, 5, 6}

    1

    Returns: 0

  9. {3, 3, 6, 7, 9}

    77

    Returns: 0

  10. {10, 8, 10, -1, 5, -1, 4, 10}

    43

    Returns: 45296

  11. {1, 7, -1, 1}

    73

    Returns: 522

  12. {7, 1}

    25

    Returns: 0

  13. {7, 7}

    99

    Returns: 184

  14. {1, 3}

    86

    Returns: 0

  15. {1, 2, 5, 6, 9, 1, 1, 7}

    46

    Returns: 536

  16. {7, 8, 5, 2, 5, 6, 9}

    1

    Returns: 0

  17. {6, 1, 7}

    45

    Returns: 76

  18. {3, 1, 4}

    29

    Returns: 50

  19. {1, 4, 5, 3, 1, 2, 9, 5, 4}

    73

    Returns: 1574

  20. {1, 7, 6}

    11

    Returns: 8

  21. {1, 6, 7}

    37

    Returns: 60

  22. {7, 7}

    99

    Returns: 184

  23. {1, 3, 2}

    86

    Returns: 166

  24. {4, 6, 3, 1, 1, 1, 5, 1, 2}

    81

    Returns: 2870

  25. {1, 1, 3, 7, 6, 7, 1, 1, 2, 2, 9}

    10

    Returns: 0

  26. {369, 165, 357, 573, 580, 545, 226, 852, 611, 388, 7, 437, 125, 291}

    550814

    Returns: 7686714

  27. {241, 797, 731, 329, 849, 689, 58, 521, 451, 101, 990, 10, 9, 651, 497, 884}

    517546

    Returns: 12365532

  28. {721, 397, 286, 0, -1, 590, 0, -1, 796, 971, 0, 222, 529, 0, -1, 963, 0}

    555774

    Returns: 1058539909

  29. {396, 385, 685, 181, -1, 111, -1, 277, 0, 213, 191, 0, 481, 253, 0, 89}

    295073

    Returns: 105632401

  30. {0, 106, 827, 370, 0, 689, 0, 891, -1, 232, 0, 753, -1, 0, 622, -1}

    544472

    Returns: 855696296

  31. {-1, 401, 133, 0, 69, 889, 733, 105, 568, 1, 0, 239, -1, -1, 961, 717, 0}

    767924

    Returns: 355698371

  32. {-1, -1, -1, -1, -1, -1, 701, -1, -1, 876, 793}

    980017

    Returns: 715337336

  33. {719, 971, 751, 806, 897, 119, 513, 37, 619, 915, 157, 241, 116, 629, 373, 770, 265}

    113173

    Returns: 5313920

  34. {149, 685, 552, 917, 479, 361, 640, 961, 251, 311, 711, 687, 121, 737}

    527431

    Returns: 5249380

  35. {961, 981, 1, 1, 681, 19, 331, 305, 653, 951, 43, 264, 857, 525, 301, 96}

    959130

    Returns: 32539238

  36. {3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357}

    949322

    Returns: 994791496

  37. {2089, 2089, 2089, 2089, 2089, 2089, 2089, 2089, 2089, 2089, 2089, 2089, 2089, 2089, 2089, 2089, 2089, 2089}

    904665

    Returns: 328884479

  38. {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    939664

    Returns: 950161410

  39. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    957668

    Returns: 957668

  40. {7677, 7677, 7677, 7677, 7677, 7677, 7677, 7677, 7677, 7677, 7677, 7677, 7677, 7677, 7677, 7677, 7677, 7677}

    954714

    Returns: 334526856

  41. {125, 357, 482}

    851001

    Returns: 1701038

  42. {529, 437, 291, 7, 291, 134, 523, 799, 611, 7291, 852, 434, 873, 227, 545, 573, 165}

    749388

    Returns: 1484194

  43. {749, 868, 217, 607, 811, 199, 681, 31, 501, 41, 137, 5697, 365, 73, 417}

    670529

    Returns: 1329664

  44. {529, 381, 286, 665, 222, 501, 613, 397, 6622, 831, 285, 971, 941}

    328646

    Returns: 644048

  45. {191, 685, 111, 181, 901, 385, 2543, 89}

    203213

    Returns: 401340

  46. {125, 357, 482}

    483

    Returns: 2

  47. {529, 437, 291, 7, 291, 134, 523, 799, 611, 7291, 852, 434, 873, 227, 545, 573, 165}

    7292

    Returns: 2

  48. {749, 868, 217, 607, 811, 199, 681, 31, 501, 41, 137, 5697, 365, 73, 417}

    5698

    Returns: 2

  49. {529, 381, 286, 665, 222, 501, 613, 397, 6622, 831, 285, 971, 941}

    6623

    Returns: 2

  50. {191, 685, 111, 181, 901, 385, 2543, 89}

    2544

    Returns: 2

  51. {3357, 6137, 8369, 1125}

    851001

    Returns: 1683014

  52. {3513, 4035, 6823, 4677, 4809, 7477}

    470546

    Returns: 919112

  53. {1269, 6434, 5149, 7134, 5784, 9135, 1605, 2252, 4291, 227, 744, 6873, 7563}

    215529

    Returns: 389914

  54. {1607, 2137, 6868, 6749, 7831, 9217, 1779, 199, 1041, 6285, 1665, 721, 9400, 4529, 3381, 1438, 6286, 3463, 6365, 4397, 5360, 963, 8222, 1613, 7677, 6417, 8646, 5907, 8796, 4576, 160, 3941, 2501, 8590, 2971}

    79501

    Returns: 78911590

  55. {0, -1, -1, -1, 9585, 2803, -1, 5310, -1, 0, 0, 0, 9576, -1, -1, -1, -1, 0, 0, 0, -1, -1, -1, -1, 8239, 5045, 0, -1, -1, -1, 7345, 3793, 748}

    202255

    Returns: 840445180

  56. {0, -1, 0, 0, 9267, 4070, 0, -1, -1, 7489, 0, 2657, -1, 8270, -1, 8793, 0, 0, 1553, 8885, -1, -1, 0, 6636}

    342369

    Returns: 1014654133

  57. {0, -1, 0, 3977, -1, 0, -1, 9126, 0, -1, 2068, 0, 0, -1, 6241, 0, -1, 7851, -1, -1, 4951, 91, -1, -1, 3991, -1, -1, 0, 2505}

    459343

    Returns: 412167181

  58. {0, 5644, -1, 0, 0, 0, 2653, 5331, -1, 0, 0, 2857, 7001, -1}

    760961

    Returns: 601061465

  59. {1445, 1701, 3961, 5309, 2713, 2376, 2561, 3941, 6799, 1818, 7482, 876, 1147, 7463, 9781, 7725, 5433, 5961, 6281, 6358, 641, 2401, 3725, 3556}

    97499

    Returns: 38465008

  60. {5692, 4310, 5500, 9457, 2575}

    777783

    Returns: 1536652

  61. {3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357, 3357}

    851001

    Returns: 609710962

  62. {5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110, 5110}

    808143

    Returns: 5809253

  63. {6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365, 6365}

    701607

    Returns: 745787990

  64. {3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134, 3134}

    581441

    Returns: 790471105

  65. {1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901, 1901}

    734385

    Returns: 1114041874

  66. {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    1000000

    Returns: 864635911

  67. {9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576, 9576}

    170279

    Returns: 141024526

  68. {3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251, 3251}

    993853

    Returns: 1083453063

  69. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    1000000

    Returns: 1000000

  70. {3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443, 3443}

    516422

    Returns: 1079906838

  71. {291, 157, 373, 188, 334, 323, 237, 52, 335, 34, 291, 69, 344, 261, 363, 11, 5, 381, 184, 26, 207, 227, 6879, 165, 129, 325, 345, 369, 329, 73, 199, 252}

    851001

    Returns: 1688244

  72. {185, 91, 151, 11, 33, 382, 381, 334, 241, 33, 395, 107, 181, 339, 186, 201, 3548, 86, 211}

    942654

    Returns: 1878212

  73. {201, 333, 265, 83, 251, 103, 386, 77, 5, 383, 382, 4386, 265, 277, 321, 177, 351, 309, 217}

    472343

    Returns: 935914

  74. {49, 193, 105, 1, 331, 78, 297, 11, 297, 247, 144, 51, 10, 5613, 7, 176, 72, 396, 190, 9, 157, 23, 289, 41, 266, 310, 106, 129, 253, 1, 383, 249, 41, 237, 119, 345}

    482891

    Returns: 954556

  75. {73, 17, 5187, 97, 170, 306, 171, 36, 219, 119, 31, 29, 197, 251, 119, 379, 141, 351, 29, 41, 189, 373, 225, 353, 65, 6, 316, 315, 237, 313, 19}

    476636

    Returns: 942898

  76. {77, 281, 195, 376, 317, 351, 1, 263, 301, 293, 85, 266, 356, 253, 353, 171, 7051, 289, 121, 1, 156, 361, 145, 161, 87, 33, 265, 361, 55, 351, 153, 297, 276}

    218042

    Returns: 421982

  77. {356, 117, 83, 125, 301, 1, 281, 97, 101, 356, 51, 32, 1, 81, 3017, 313, 183, 145, 69, 61, 263}

    76799

    Returns: 147564

  78. {71, 351, 309, 17, 121, 63, 34, 9, 5, 380, 301, 273, 26, 81, 334, 377, 159, 301, 382, 116, 137, 276, 295, 48, 317, 286, 67, 76, 285, 5586, 89}

    566657

    Returns: 1122142

  79. {63, 79, 148, 261, 151, 89, 126, 245, 177, 311, 46, 278, 297, 65, 225, 129, 48, 361, 148, 90, 324, 161, 361, 213, 269, 4941, 125, 151}

    955201

    Returns: 1900520

  80. {221, 264, 22, 1, 337, 3084, 185, 49, 391, 88, 170, 229, 134, 333, 291, 161, 11, 61, 136}

    463745

    Returns: 921322

  81. {291, 157, 373, 188, 334, 323, 237, 52, 335, 34, 291, 69, 344, 261, 363, 11, 5, 381, 184, 26, 207, 227, 6879, 165, 129, 325, 345, 369, 329, 73, 199, 252}

    6880

    Returns: 2

  82. {185, 91, 151, 11, 33, 382, 381, 334, 241, 33, 395, 107, 181, 339, 186, 201, 3548, 86, 211}

    3549

    Returns: 2

  83. {201, 333, 265, 83, 251, 103, 386, 77, 5, 383, 382, 4386, 265, 277, 321, 177, 351, 309, 217}

    4387

    Returns: 2

  84. {49, 193, 105, 1, 331, 78, 297, 11, 297, 247, 144, 51, 10, 5613, 7, 176, 72, 396, 190, 9, 157, 23, 289, 41, 266, 310, 106, 129, 253, 1, 383, 249, 41, 237, 119, 345}

    5614

    Returns: 2

  85. {73, 17, 5187, 97, 170, 306, 171, 36, 219, 119, 31, 29, 197, 251, 119, 379, 141, 351, 29, 41, 189, 373, 225, 353, 65, 6, 316, 315, 237, 313, 19}

    5188

    Returns: 2

  86. {77, 281, 195, 376, 317, 351, 1, 263, 301, 293, 85, 266, 356, 253, 353, 171, 7051, 289, 121, 1, 156, 361, 145, 161, 87, 33, 265, 361, 55, 351, 153, 297, 276}

    7052

    Returns: 2

  87. {356, 117, 83, 125, 301, 1, 281, 97, 101, 356, 51, 32, 1, 81, 3017, 313, 183, 145, 69, 61, 263}

    3018

    Returns: 2

  88. {71, 351, 309, 17, 121, 63, 34, 9, 5, 380, 301, 273, 26, 81, 334, 377, 159, 301, 382, 116, 137, 276, 295, 48, 317, 286, 67, 76, 285, 5586, 89}

    5587

    Returns: 2

  89. {63, 79, 148, 261, 151, 89, 126, 245, 177, 311, 46, 278, 297, 65, 225, 129, 48, 361, 148, 90, 324, 161, 361, 213, 269, 4941, 125, 151}

    4942

    Returns: 2

  90. {221, 264, 22, 1, 337, 3084, 185, 49, 391, 88, 170, 229, 134, 333, 291, 161, 11, 61, 136}

    3085

    Returns: 2

  91. {1437, 9388, 7226, 2031, 6873, 8165, 227, 9135, 9573, 6434, 1605, 5529, 1125, 9611, 1269, 2252, 5681, 7563, 4291, 3981, 7007, 7799, 529, 5784, 8369, 5545, 6291, 9061, 744, 1283, 1073, 3811, 1523, 852, 3357, 7134}

    1000000

    Returns: 678726434

  92. {1112, 3956, 2137, 2151, -1, 1201, 5582, 7933, 7385, 3936, 903, 1441, 7781, 6010, 1391, 2343, 7921, 3551, 5851, 1017, 9691, 6833, 8795, 9338, 9982, 2201, 8519, 7011, 2005, 1277, 4677, 3134, 5683, 6665, 8386, 6309}

    1000000

    Returns: 782346801

  93. {3105, 9608, 8239, 7989, 5623, 1399, 2803, 4733, 7889, 2023, 4961, 9680, 2876, 6171, 9585, 2390, 9097, 9601, 831, 2369, 1681, 3625, 3401, 1871, 943, 7489, 2866, 6001, 5721, 4717, 6069, 8239, 414, 9133, 5045, 7979}

    1000000

    Returns: 777582056

  94. {6167, 7697, 9126, 4225, 7851, 3991, 8469, 4951, 2068, 2407, 2311, 7677, 5677, 9822, 3483, 8517, 2639, 1697, 5786, 8337, 7715, 2505, 8429, 320, -1, 0, 0, -1, 1448, 9343, 6847, 676, 2983, 1136, 1129, 91}

    1000000

    Returns: 57854999

  95. {6353, 1404, 3551, 641, 717, 7482, 5361, 7089, 6681, 376, 6358, 3753, 6887, 876, 1818, 3156, 3601, 9745, 7499, 7633, 571, 9781, 877, 1853, 2713, 4595, 7161, 6751, 5433, 5309, 3961, 55, 1561, 7725, 8885, 2376}

    1000000

    Returns: 385529514

  96. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    1000000

    Returns: 422248963

  97. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    2

    Returns: 2

  98. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    1

    Returns: 0

  99. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    7

    Returns: 541198094

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

    100

    Returns: 429221060

  101. {25,24,46,86,64,64,77,17,98,48,42,73,26,49,80,53,61,9,98,7,100,75,84,83,44,27,97,47,54,16,21,83,80,92,81,97}

    1000000

    Returns: 1133902184

  102. {68,35,75,68,62,12,54,42,75,56,29,38,66,53,68,79,18,45,45,39,74,15,44,32,36,47,35,12,58,64,53,53,79,32,10,25}

    1000000

    Returns: 5165199

  103. {59,14,88,46,16,66,63,47,56,103,77,104,97,74,60,37,17,43,64,44,97,105,71,24,84,47,80,114,112,33,104,101,112,98,88,23}

    1000000

    Returns: 242997179

  104. {50,11,6,27,39,68,21,20,72,30,31,49,21,8,48,50,12,6,7,4,51,56,8,25,66,42,52,13,52,68,6,39,66,55,72,55}

    1000000

    Returns: 411723968

  105. {9961,9997,9899,9915,9902,9959,9930,9962,9957,9933,9970,9984,9925,9948,9996,9977,9896,9924,9902,9989,9900,9970,9903,9925,9963,9932,9923,9953,9919,9995,9998,9910,9942,9900,9986,9923}

    1000000

    Returns: 857756246

  106. {24,108,35,75,83,14,76,80,86,67,55,89,38,87,20,13,119,83,31,21,105,118,88,112,8,15,65,66,76,20,51,90,41,53,29,47}

    1000000

    Returns: 345153375

  107. {43,55,52,35,39,50,46,48,49,51,31,42,36,53,50,40,32,56,41,37,54,35,51,30,49,39,35,52,39,33,44,36,30,40,47,46}

    1000000

    Returns: 1174698316

  108. {28,16,49,6,43,37,42,38,27,29,43,49,7,23,41,15,52,18,30,34,51,42,9,28,30,50,46,41,26,47,43,38,3,51,11,45}

    1000000

    Returns: 515311615

  109. {22,14,28,19,15,7,24,39,30,30,51,34,52,24,7,11,16,25,6,31,15,26,13,49,9,29,27,39,18,30,19,17,7,28,18,11}

    1000000

    Returns: 950405474

  110. {47,49,9,34,24,42,14,53,39,34,49,44,20,13,51,25,45,37,21,20,31,29,42,51,17,19,52,50,41,50,11,32,18,17,28,22}

    1000000

    Returns: 625759223

  111. {1,2,2,1,2,0,0,2,0}

    59

    Returns: 660

  112. {2,2,2,3,1,0,3,1}

    81

    Returns: 1208

  113. {0,5,5,4,4}

    10

    Returns: 12

  114. {0,0,1,1,1,1}

    42

    Returns: 242

  115. {0,2,3,0,1}

    9

    Returns: 12

  116. {3454, 3451, 2454, 4554, 3754, 9964, 9934, 9933, 1, 9934, 0, 3454, 3454, 3454, 2358, 123, 548, 8957, 1237, 1271, 7311, 3984, 1237, 3456, 3423, 1235, 3426, 1234, 6756, 3485, 1231, 0, 0, 1237, 3425, 1238 }

    1000000

    Returns: 0

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: