Statistics

Problem Statement for "CharmingTickets"

Problem Statement

A ticket number that contains exactly 2*K digits is called charming if and only if at least one of the following conditions is satisfied:

  • The sum of the first K digits is equal to the sum of the last K digits.
  • The sum of all the digits at positions with odd indices is equal to the sum of all the digits at positions with even indices.

Also, you think that some digits are better than others, so a charming number must contain only digits that you consider to be good. These digits are given in the String good. Determine the number of different charming numbers containing exactly 2*K digits. Return this number modulo 999983. Remember that ticket numbers may contain leading zeroes.

Definition

Class:
CharmingTickets
Method:
count
Parameters:
int, String
Returns:
int
Method signature:
int count(int K, String good)
(be sure your method is public)

Constraints

  • K will be between 1 and 1000, inclusive.
  • good will contain between 1 and 10 characters, inclusive.
  • good will contain only digits ('0' - '9').
  • All characters in good will be distinct.

Examples

  1. 1

    "0123456789"

    Returns: 10

    Only "XX" numbers are charming.

  2. 2

    "21"

    Returns: 8

    Only 1111, 1122, 1212, 1221, 2112, 2121, 2211, 2222 are charming numbers.

  3. 2

    "0987654321"

    Returns: 1240

  4. 137

    "0123456789"

    Returns: 630063

  5. 1000

    "0123456789"

    Returns: 495241

    max test

  6. 1000

    "8"

    Returns: 1

    border case: single digit

  7. 1

    "2"

    Returns: 1

    border case: single digit

  8. 123

    "8123"

    Returns: 894140

    digits aren't sorted

  9. 971

    "82109467"

    Returns: 166953

    digits aren't sorted

  10. 344

    "01459"

    Returns: 602881

  11. 714

    "124"

    Returns: 295799

  12. 497

    "03489"

    Returns: 488908

  13. 668

    "1249"

    Returns: 477485

  14. 870

    "1456"

    Returns: 528790

  15. 844

    "01234579"

    Returns: 364947

  16. 698

    "2356789"

    Returns: 190291

  17. 241

    "06789"

    Returns: 163911

  18. 544

    "0235689"

    Returns: 885452

  19. 133

    "1345678"

    Returns: 802975

  20. 331

    "01379"

    Returns: 441028

  21. 624

    "378"

    Returns: 968384

  22. 497

    "268"

    Returns: 503714

  23. 827

    "01247"

    Returns: 657824

  24. 164

    "13478"

    Returns: 744157

  25. 69

    "013468"

    Returns: 638607

  26. 454

    "23456789"

    Returns: 544434

  27. 798

    "0124678"

    Returns: 790574

  28. 515

    "0345789"

    Returns: 799664

  29. 804

    "134678"

    Returns: 802394

  30. 441

    "34567"

    Returns: 275003

  31. 825

    "35678"

    Returns: 269447

  32. 478

    "23479"

    Returns: 168286

  33. 416

    "123456"

    Returns: 299125

  34. 625

    "127"

    Returns: 542970

  35. 333

    "017"

    Returns: 246964

  36. 680

    "35"

    Returns: 313797

  37. 504

    "36"

    Returns: 427660

  38. 797

    "03458"

    Returns: 2384

  39. 858

    "23789"

    Returns: 60151

  40. 256

    "1479"

    Returns: 206840

  41. 88

    "0158"

    Returns: 472753

  42. 999

    "012489"

    Returns: 523582

  43. 124

    "1236789"

    Returns: 771748

  44. 572

    "056"

    Returns: 599803

  45. 488

    "1678"

    Returns: 678740

  46. 924

    "135689"

    Returns: 517709

  47. 871

    "0128"

    Returns: 287954

  48. 693

    "159"

    Returns: 239627

  49. 852

    "13469"

    Returns: 880393

  50. 82

    "01249"

    Returns: 969980

  51. 759

    "014679"

    Returns: 228180

  52. 155

    "167"

    Returns: 77111

  53. 112

    "03568"

    Returns: 844094

  54. 754

    "01245"

    Returns: 163928

  55. 991

    "0123568"

    Returns: 149620

  56. 793

    "12346789"

    Returns: 824626

  57. 54

    "134567"

    Returns: 41292

  58. 917

    "012458"

    Returns: 287836

  59. 637

    "12459"

    Returns: 354079

  60. 951

    "915274"

    Returns: 843299

  61. 994

    "16380"

    Returns: 851803

  62. 940

    "31"

    Returns: 779467

  63. 975

    "4621058"

    Returns: 109284

  64. 905

    "691324"

    Returns: 365437

  65. 911

    "5620"

    Returns: 630933

  66. 981

    "074196"

    Returns: 560739

  67. 975

    "82"

    Returns: 374506

  68. 971

    "7"

    Returns: 1

  69. 922

    "7"

    Returns: 1

  70. 923

    "51208"

    Returns: 711795

  71. 980

    "967"

    Returns: 445137

  72. 960

    "210479"

    Returns: 849236

  73. 935

    "45728"

    Returns: 781311

  74. 928

    "6145"

    Returns: 118977

  75. 976

    "736"

    Returns: 308731

  76. 911

    "6910"

    Returns: 40764

  77. 985

    "7"

    Returns: 1

  78. 953

    "017"

    Returns: 186397

  79. 989

    "327860"

    Returns: 896026

  80. 954

    "30165"

    Returns: 482722

  81. 904

    "8"

    Returns: 1

  82. 923

    "3729540"

    Returns: 306376

  83. 954

    "89576"

    Returns: 565142

  84. 912

    "941603"

    Returns: 456578

  85. 961

    "541"

    Returns: 83565

  86. 963

    "41"

    Returns: 865968

  87. 985

    "5"

    Returns: 1

  88. 967

    "624"

    Returns: 807788

  89. 975

    "269"

    Returns: 74120

  90. 1000

    "0124568"

    Returns: 80329

  91. 999

    "012345678"

    Returns: 509255

  92. 995

    "0251947"

    Returns: 95279

  93. 1000

    "8302457"

    Returns: 4446

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: