Statistics

Problem Statement for "ConversionMachine"

Problem Statement

You are given two words, word1 and word2, of equal length. Their alphabet consists of only "a", "b", and "c" (quotes for clarity). You may change some characters into others for a specific cost:
  • The cost to change "a" to "b", is costs[0].
  • The cost to change "b" to "c", is costs[1].
  • The cost to change "c" to "a", is costs[2].
The remaining operations are not possible.

You are given the Strings word1 and word2, the int[] costs, and an int maxCost. Find the total number of sequences of moves that can change word1 into word2 with a total cost of at most maxCost, inclusive. Return it modulo 1000000007 (10^9+7). Two sequences of moves are different if their number of moves differ or if for some k the k-th move in one sequence changes a different position than the k-th move in the other sequence.

Definition

Class:
ConversionMachine
Method:
countAll
Parameters:
String, String, int[], int
Returns:
int
Method signature:
int countAll(String word1, String word2, int[] costs, int maxCost)
(be sure your method is public)

Notes

  • Each letter can be changed multiple times.
  • Even if a letter currently matches the corresponding letter in word2, it can still be changed.

Constraints

  • word1 and word2 will contain the same number of characters.
  • word1 and word2 will each contain between 1 and 11 characters, inclusive.
  • Each character in word1 and word2 will be 'a', 'b' or 'c'.
  • costs will contain exactly 3 elements.
  • Each element of costs will be between 1 and 1000000000 (10^9), inclusive.
  • maxCost will be between 0 and 1000000000 (10^9), inclusive.

Examples

  1. "a"

    "b"

    {100,2,3}

    205

    Returns: 2

    There are two sequences of moves with a total cost of at most 205: - "a" -> "b" (Total cost = 100). - "a" -> "b" -> "c" -> "a" -> "b". (Total cost = 205).

  2. "aa"

    "bb"

    {102, 283, 282}

    1000000

    Returns: 394255315

  3. "abcba"

    "abcba"

    {67,23,43}

    0

    Returns: 1

    Since the two words are equal, the empty sequence of moves is valid.

  4. "aaaaaaaaaaa"

    "cbcbaaaacaa"

    {1,1,1}

    1000000000

    Returns: 103255104

  5. "cccccccc"

    "aaaaaaaa"

    {10000000,1,1}

    100

    Returns: 40320

  6. "aa"

    "cc"

    {1,10,100}

    1787

    Returns: 123611681

  7. "a"

    "c"

    {2374035,562618982,480360678}

    780797507

    Returns: 1

  8. "a"

    "c"

    {842433666,48442207,178097042}

    747333495

    Returns: 0

  9. "acacaaaabc"

    "bcbabcbbbb"

    {884741355,762905410,766344689}

    614762568

    Returns: 0

  10. "ccbbacbab"

    "acbccacba"

    {44749443,321083036,286939056}

    309527907

    Returns: 0

  11. "aabccccbc"

    "caabacbcb"

    {387764413,236012499,201750066}

    501823287

    Returns: 0

  12. "ca"

    "ca"

    {541156591,35726091,946191342}

    859654263

    Returns: 1

  13. "bacac"

    "caaac"

    {686515006,386481844,826460406}

    519511330

    Returns: 0

  14. "bca"

    "bcc"

    {932934013,401587205,264489679}

    982138130

    Returns: 0

  15. "abbabc"

    "ccabcc"

    {226966362,956249242,739687284}

    365977640

    Returns: 0

  16. "baba"

    "bbbc"

    {669944122,34483038,619280588}

    695148743

    Returns: 0

  17. "baca"

    "ccaa"

    {54,84,14}

    307597668

    Returns: 721882592

  18. "cbaaca"

    "cbbcca"

    {61,75,88}

    815144539

    Returns: 309483399

  19. "ca"

    "aa"

    {62,19,50}

    195602524

    Returns: 860183739

  20. "cccaaaccba"

    "cbaaccbaab"

    {61,45,47}

    338999268

    Returns: 736706045

  21. "cbcccaaccca"

    "ccbcccaaaba"

    {59,7,52}

    90283387

    Returns: 532665495

  22. "bbbcab"

    "cbccba"

    {22,47,70}

    538114877

    Returns: 261779849

  23. "aaabb"

    "cbcac"

    {80,63,18}

    221027581

    Returns: 896129862

  24. "ca"

    "ac"

    {67,58,57}

    773343718

    Returns: 613955220

  25. "aabbcacb"

    "bcaabbab"

    {60,100,31}

    758794666

    Returns: 236712319

  26. "bcabbabcbb"

    "cbbbbacbca"

    {74,47,45}

    567626576

    Returns: 590427414

  27. "abbcaaccbbc"

    "bcacbaabbaa"

    {1,1,1}

    704180870

    Returns: 247948065

  28. "bcabcacacca"

    "acaabbbacbc"

    {1,1,1}

    411951430

    Returns: 855738145

  29. "caccaccaabb"

    "bbcccbaaacc"

    {1,1,1}

    598698049

    Returns: 144538037

  30. "accbbbbbaac"

    "baabaaabcba"

    {1,1,1}

    452139813

    Returns: 792140212

  31. "cbbbcccacca"

    "ccabcabbaab"

    {1,1,1}

    425008849

    Returns: 178523401

  32. "babbacbcbcc"

    "cbbabacccbb"

    {1,1,1}

    632248484

    Returns: 532322220

  33. "bcbbbcbaccb"

    "aaccabccbcc"

    {1,1,1}

    284761269

    Returns: 321601669

  34. "bcabbcbbaac"

    "bbbcccbabac"

    {1,1,1}

    277834411

    Returns: 41318521

  35. "abcbbcbcabc"

    "cccabbbbcab"

    {1,1,1}

    536870911

    Returns: 515131206

  36. "cbcacbcacaa"

    "caaabcccbbc"

    {1,1,1}

    1000000000

    Returns: 334944992

  37. "aaaaaaaaaaa"

    "aaaaaaaaaaa"

    {1,1,1}

    536870912

    Returns: 941170882

  38. "aabbabbbbbb"

    "bbababaabab"

    {783,635,967}

    177015953

    Returns: 340935804

  39. "bbbabbbbbaa"

    "aababbbbaab"

    {47,816,934}

    222754718

    Returns: 742845138

  40. "abaabbabbaa"

    "aaabbbbbbbb"

    {801,243,927}

    470199726

    Returns: 727541367

  41. "babaaabbbbb"

    "baababaabba"

    {744,389,145}

    905483689

    Returns: 98864847

  42. "ababaaaabab"

    "aaabbbabaaa"

    {12,606,645}

    120370484

    Returns: 834214937

  43. "abbaaaabbbb"

    "aaabaabbabb"

    {614,131,274}

    683441231

    Returns: 272907888

  44. "bbbbaaaaaba"

    "bbbaabbbaaa"

    {264,278,63}

    843591678

    Returns: 685526135

  45. "abbaabbbbba"

    "abbbbabaaab"

    {415,126,396}

    287817727

    Returns: 159352612

  46. "aabaaabbaaa"

    "bbababababb"

    {479,485,951}

    603678491

    Returns: 353709000

  47. "bbaaaaabbab"

    "ababbabbaab"

    {705,736,818}

    215275678

    Returns: 64933726

  48. "aaaaaaaabbb"

    "bbbabababba"

    {937,692,443}

    163296300

    Returns: 461696016

  49. "bbbaaababbb"

    "bbabbbaabab"

    {701,260,746}

    600554940

    Returns: 168301926

  50. "bbababaabba"

    "aababbbabba"

    {543,806111111,516222222}

    406387153

    Returns: 0

  51. "bbbbabaaabb"

    "abbabbbbaaa"

    {920,8031111,5891111}

    184101707

    Returns: 305611725

  52. "bbaaabbbaaa"

    "bbbbabbbaab"

    {690,80511111,3011111}

    627536534

    Returns: 776178791

  53. "aabbbaaaaab"

    "bbbbaaaabbb"

    {531,4144444,818444}

    209222160

    Returns: 97373708

  54. "baabbabbbab"

    "aabaaaabbab"

    {673,1,93012334}

    975679429

    Returns: 645858550

  55. "abbabbbbbbb"

    "baaaaabaaab"

    {441,7791111,781}

    508653228

    Returns: 462187799

  56. "bbaaaabbbba"

    "baababbbbbb"

    {375,740,12212334}

    532008079

    Returns: 346534130

  57. "abaabbbaaba"

    "baabbaabaaa"

    {481,293,705000542}

    367517558

    Returns: 0

  58. "ab"

    "ab"

    {729,371,886}

    640035947

    Returns: 688082579

  59. "a"

    "b"

    {514,12,817}

    138068217

    Returns: 102806

  60. "ba"

    "aa"

    {241,811,869}

    504932238

    Returns: 201998554

  61. "aabbb"

    "babab"

    {892,185,692}

    382931508

    Returns: 947998483

  62. "b"

    "a"

    {317,485,769}

    850555421

    Returns: 541410

  63. "bb"

    "bb"

    {226,852,336}

    404236895

    Returns: 153777955

  64. "aba"

    "baa"

    {577,256,790}

    186976621

    Returns: 219306955

  65. "bbaba"

    "ababb"

    {190,948,389}

    110884805

    Returns: 137201130

  66. "aba"

    "bbb"

    {865,273,630}

    829228040

    Returns: 111789378

  67. "a"

    "b"

    {368,51,369}

    252574603

    Returns: 320526

  68. "bbbaaaaaa"

    "acacaacaa"

    {2,74,41}

    582996071

    Returns: 128360629

  69. "ababbbbab"

    "accacaaaa"

    {11,72,90}

    608326079

    Returns: 869943179

  70. "aabbbbbab"

    "acccacccc"

    {84,20,82}

    861168166

    Returns: 654379334

  71. "aaabababbba"

    "aaaacacccca"

    {91,85,3}

    995987791

    Returns: 914723037

  72. "baabbabaab"

    "cacaaacaca"

    {70,3,99}

    576911789

    Returns: 264820392

  73. "baaabbaabab"

    "ccacaaaccac"

    {40,40,61}

    927150898

    Returns: 484973990

  74. "baaaababaab"

    "ccaaacccaca"

    {36,100,52}

    902260170

    Returns: 527130575

  75. "abaababab"

    "ccaacaaac"

    {54,27,2}

    163638604

    Returns: 42848010

  76. "abbababaaa"

    "cacaccaaaa"

    {92,84,4}

    152428362

    Returns: 998473549

  77. "bababbaaba"

    "accacccaca"

    {61,65,86}

    669453338

    Returns: 260431374

  78. "bbaccbbb"

    "bbacbbac"

    {70437,133,133}

    991840667

    Returns: 89619301

  79. "aaaa"

    "bbbb"

    {1000000000, 1, 1 }

    1000000000

    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: