back to the menu

Flag Counter TopCoder SRM 572 - 1000: NextAndPrev

SRM 572 1 1000 NextAndPrev


Problem Statement

给定一个字符串,然后给定一个目标串,
每一次可以讲所有的相同字符+1或者-1,其中z+1=a
给定+1的代价和-1的代价,然后你要计算出最小的代价。

Consider a string consisting of lowercase characters and following two operations that can change it:
  • Next: Choose a lowercase character and replace its every occurrence with the next character. The next character of 'z' is 'a' ('a' -> 'b', 'b' -> 'c', ..., 'y' -> 'z', 'z' -> 'a').
  • Prev: Choose a lowercase character and replace its every occurrence with the previous character. The previous character of 'a' is 'z' ('a' -> 'z', 'b' -> 'a', ..., 'y' -> 'x', 'z' -> 'y').
You can use each operation as many times as you want, and in any order you like. You are given ints nextCost and prevCost. These represent the cost of using each Next and Prev operation, respectively. You are also given two Strings start and goal. Return the minimum cost required in order to transform start into goal using the above operations. If transforming start into goal is impossible, return -1 instead.

Definition

(be sure your method is public)

Limits

Constraints

Test cases

  1. input
    • nextCost 5
    • prevCost 8
    • start "aeaae"
    • goal "bcbbc"
    output
    Returns 21
    note
    There are several optimal sequences of operations. Here is one of them: "aeaae" -(Next)-> "bebbe" -(Prev)-> "bdbbd" -(Prev)-> "bcbbc". The total cost is 5 + 8 + 8 = 21.
  2. input
    • nextCost 5
    • prevCost 8
    • start "aeaae"
    • goal "bccbc"
    output
    Returns -1
    note
    It is impossible to transform "aeaae" into "bccbc".
  3. input
    • nextCost 1
    • prevCost 1
    • start "srm"
    • goal "srm"
    output
    Returns 0
    note
    start and goal may be the same. The cost of an empty sequence of operations is 0.
  4. input
    • nextCost 1000
    • prevCost 39
    • start "a"
    • goal "b"
    output
    Returns 975
  5. input
    • nextCost 123
    • prevCost 456
    • start "pqrs"
    • goal "abab"
    output
    Returns -1
  6. input
    • nextCost 100
    • prevCost 19
    • start "topcoder"
    • goal "ssszsffs"
    output
    Returns 676
  7. input
    • nextCost 1
    • prevCost 1000
    • start "csk"
    • goal "wog"
    output
    Returns 64
  8. input
    • nextCost 7
    • prevCost 6
    • start "qwerty"
    • goal "jjjjjj"
    output
    Returns 125
  9. input
    • nextCost 306
    • prevCost 26
    • start "me"
    • goal "ii"
    output
    Returns 572

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)2003, TopCoder, Inc. All rights reserved.