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 the strings 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". |
Definition |
| | | Class: | EasyConversionMachine | | Method: | isItPossible | | Parameters: | string, string, int | | Returns: | string | | Method signature: | string isItPossible(string originalWord, string finalWord, int k) | | (be sure your method is public) | |
| |
|
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) |
|
| | | | Returns: "IMPOSSIBLE" | | It is not possible to reach finalWord in fewer than 4 moves. | | |
| 1) |
|
| | | | Returns: "IMPOSSIBLE" | | The number of moves must be exactly k=1. | | |
| 2) |
|
| | | | Returns: "POSSIBLE" | | Use each move to change each of the letters once. | | |
| 3) |
|
| | | | Returns: "POSSIBLE" | The following sequence of 4 moves does the job:
aaa -> baa -> bab -> aab -> bab | | |
| 4) |
|
| | "aababbabaa" | "abbbbaabab" | 9 | | Returns: "IMPOSSIBLE" | | | |
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.
字符串水題！
249.23PT！?。?/p>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define swap(t,x,y) (t=x,x=y,y=t)
#define clr(list) memset(list,0,sizeof(list))
using namespace std;
class EasyConversionMachine{
public:
string isItPossible(string originalWord, string finalWord, int k)
{
int n=originalWord.size();
int tot=0;
for (int i=0;i<n;i++)
if (originalWord[i]!=finalWord[i])
tot++;
if (tot<=k && (k-tot)%2==0) //傻叉，這里剛剛開始搞反了，testing WA了一次
return "POSSIBLE";
return "IMPOSSIBLE";
}
};