시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 1201 | 623 | 488 | 57.344% |
좋은 문자열은 다음과 같이 정의된다.
어떤 두 좋은 문자열 A와 B가 주어진다. 문자열 A를 '인접한 두 문자를 서로 바꾸는' 연산을 통해 문자열 B로 바꾸려고 한다. 이때 필요한 연산의 수를 구하는 프로그램을 작성하시오. A를 B로 바꾸는 중에 나타나는 문자열도 모두 좋은 문자열이어야 한다.
예를 들어, A = aabbabab 이고 B = aaaabbbb라 해 보자. 그렇다면 다음과 같이 5번의 연산을 통해 A를 B로 변환할 수 있다.
aabbabab → aabbaabb → aabababb → aabaabbb → aaababbb → aaaabbbb
첫 줄에 테스트 케이스의 수 T가 주어진다.
각각의 테스트 케이스마다, 한 줄에 문자열 A, B가 공백으로 분리되어 주어진다. 이때 A와 B는 좋은 문자열이며, 각각의 길이는 2 이상 100,000 이하이다.
T줄에 걸쳐서, 각 테스트 케이스에서 주어진 문자열 A를 문자열 B로 변환할 때 필요한 연산의 수를 출력하시오.
만약 변환이 불가능한 경우 -1을 출력한다.
2 aabbabab aaaabbbb aabbab abaabb
5 2
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2014 H번