EasyConversionMachine
SRM 550 · 2012-06-05 · by vexorian
SRM 550 · 2012-06-05 · by vexorian · Simple Math
Problem Statement
Problem Statement
We have a String originalWord. Each character of originalWord is either 'a' or 'b'. Timmy claims that he can convert it to finalWord using exactly k moves. In each move, he can either change a single 'a' to a 'b', or change a single 'b' to an 'a'.
You are given theString s originalWord and finalWord, and the int k. Determine whether Timmy may be telling the truth.
If there is a possible sequence of exactly k moves that will turn originalWord into finalWord, return "POSSIBLE" (quotes for clarity).
Otherwise, return "IMPOSSIBLE".
You are given the
Notes
- Timmy may change the same letter multiple times. Each time counts as a different move.
Constraints
- originalWord will contain between 1 and 50 characters, inclusive.
- finalWord and originalWord will contain the same number of characters.
- Each character in originalWord and finalWord will be 'a' or 'b'.
- k will be between 1 and 100, inclusive.
Examples
0)
"aababba" "bbbbbbb" 2 Returns: "IMPOSSIBLE"
It is not possible to reach finalWord in fewer than 4 moves.
1)
"aabb" "aabb" 1 Returns: "IMPOSSIBLE"
The number of moves must be exactly k=1.
2)
"aaaaabaa" "bbbbbabb" 8 Returns: "POSSIBLE"
Use each move to change each of the letters once.
3)
"aaa" "bab" 4 Returns: "POSSIBLE"
The following sequence of 4 moves does the job: aaa -> baa -> bab -> aab -> bab
4)
"aaa" "bab" 5 Returns: "IMPOSSIBLE"
Submissions are judged against all 215 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class EasyConversionMachine with a public method string isItPossible(string originalWord, string finalWord, int k) · 215 test cases · 2 s / 256 MB per case