실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
농부 현수의 사촌 현우는 조금 특이한 과학자입니다. 그는 가족 모임에서 많은 갈등을 일으키지만, 농부 현수의 소들과 관련된 문제에 직면했을 때 해결하는 데 도움을 줍니다.
현재 현수는 소들과 관련된 문제를 겪고 있습니다. 그는 최근 마리의 소 ()를 주문했는데, 이들은 Holsteins과 Guernsey 두 가지 품종으로 구성되어 있습니다. 그는 주문한 소들을 H(Holsteins을 나타냄) 또는 G(Guernsey를 나타냄)로 구성된 개의 문자열로 표시했습니다. 하지만 불행히도, 소들이 그의 농장에 도착하여 줄을 세웠을 때, 그들의 품종은 이 원래 문자열과 다른 문자열을 형성했습니다.
이제 두 문자열을 와 라고 부르자고 했을 때, 여기서 는 현수가 원래 원했던 품종 식별자의 문자열이고, 는 소들이 도착했을 때 보이는 문자열입니다. 현수가 의 소들을 재배열하여 를 얻는 것이 충분한지 단순히 확인하는 대신, 그는 사촌 현우에게 과학적 지식을 활용하여 문제를 해결하도록 요청합니다.
몇 달 동안의 작업 끝에 현우는 놀라운 기계, 다중 소 품종 전환기 3000을 만들었습니다. 이 기계는 어떤 소의 부분 문자열이든 선택하고 그 품종을 전환하는 기능을 가지고 있습니다: 부분 문자열에서 모든 H는 G가 되고, 모든 G는 H가 됩니다.
현수는 현재의 순서 를 원래 원했던 순서 로 변환하기 위해 이 기계를 최소 몇 번 사용해야 하는지 알고 싶습니다.
하지만 현우는 독특한 과학 기계를 만들어주기만 할 뿐, 당신이 현수의 문제를 기계를 사용하여 해결하는 데 도움을 주어야합니다.
입력의 첫 번째 줄에는 이 포함되어 있고, 그 다음 두 줄에는 문자열 와 가 있습니다. 각 문자열은 H 또는 G로 구성된 개의 문자를 가지고 있습니다.
를 로 변환하기 위해 기계를 적용해야 하는 최소 횟수를 출력합니다.
7 GHHHGHH HHGGGHH
2
첫째로, 현수는 첫 번째 문자에 해당하는 부분 문자열만을 변환할 수 있어, 를 GHGGGHH로 변환할 수 있습니다.
그 다음에는, 세 번째와 네 번째 문자로 이루어진 부분 문자열을 변환하면 가 됩니다.
물론, 기계를 두 번 사용하는 다른 조합들도 작동합니다.
출처: USACO 2020 February Contest, Bronze Problem 2. Mad Scientist