레이팅 미적용베시는 텍스트 편집 소프트웨어의 최신 최고 혁신인 miV를 사용하고 있다! 그녀는 영어 대소문자만으로 이루어진 입력 문자열에서 시작해 이를 어떤 출력 문자열로 변환하고 싶어 한다. miV에서는 키를 한 번 눌러 문자열에 등장하는 어떤 영어 문자 \(c_1\)의 모든 출현을 다른 영어 문자 \(c_2\)로 바꿀 수 있다. 예를 들어 문자열 \(\texttt{aAbBa}\)에서 베시가 \(c_1\)을 'a', \(c_2\)를 'B'로 선택하면, 주어진 문자열은 \(\texttt{BAbBB}\)로 변환된다.
베시는 바쁜 소이므로, \(T\) (\(1\le T\le 10\))개의 독립적인 테스트 케이스 각각에 대해, 입력 문자열을 원하는 출력 문자열로 변환하는 데 필요한 최소 키 입력 횟수를 출력하여라.
Problem credits: Benjamin Qi
채점 방식
- 입력 2-6: 모든 문자열의 길이는 최대 \(50\)이다.
- 입력 7-9: 모든 문자열은 소문자 '\(\texttt{a}\)'부터 '\(\texttt{e}\)'까지로만 이루어진다.
- 입력 10-15: 추가 제약이 없다.
Problem credits: Benjamin Qi
첫째 줄에 독립적인 테스트 케이스의 수 \(T\)가 주어진다.
다음 \(T\)쌍의 줄에는 길이가 같은 입력 문자열과 출력 문자열이 주어진다. 모든 문자는 영어 대문자 또는 소문자이다 (A부터 Z 또는 a부터 z). 모든 문자열의 길이의 합은 \(10^5\)를 넘지 않는다.
각 테스트 케이스에 대해, 입력 문자열을 출력 문자열로 바꾸는 데 필요한 최소 키 입력 횟수를 출력하고, 불가능하면 \(-1\)을 출력한다.
4
abc
abc
BBC
ABC
abc
bbc
ABCD
BACD0
-1
1
3The first input string is the same as its output string, so no keystrokes are
required.
The second input string cannot be changed into its output string because Bessie
cannot change one '\(\texttt{B}\)' to '\(\texttt{A}\)' while keeping the other as
'\(\texttt{B}\)'.
The third input string can be changed into its output string by changing
'\(\texttt{a}\)' to '\(\texttt{b}\)'.
The last input string can be changed into its output string like so:
\(\texttt{ABCD} \rightarrow \texttt{EBCD} \rightarrow \texttt{EACD} \rightarrow \texttt{BACD}\).
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > January > Silver