31433번 - KSA 문자열 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 2141 | 405 | 328 | 21.867% |
문제
KSAAC 운영진은 모두 KSA를 사랑하기 때문에 다음과 같은 조건을 만족하는 문자열을 좋아한다.
문자열의 길이를 $N$이라고 할 때, $1\leq i\leq N$인 모든 $i$에 대하여
- $i$를 $3$으로 나눈 나머지가 $1$이면 $i$번째 문자는
K이다. - $i$를 $3$으로 나눈 나머지가 $2$이면 $i$번째 문자는
S이다. - $i$를 $3$으로 나눈 나머지가 $0$이면 $i$번째 문자는
A이다.
문자열에는 다음과 같은 시행을 $0$회 이상 수행할 수 있다.
- 존재하는 아무 문자를 한 개 제거한다.
- 맨 앞에 아무 문자를 한 개 추가한다.
- 맨 뒤에 아무 문자를 한 개 추가한다.
주어진 문자열 $X$에 적절한 시행을 하여 $X$를 $X$와 길이가 같으면서 KSAAC 운영진이 좋아하는 문자열로 바꾸려고 한다. 이때 필요한 시행의 최소 횟수를 구하여라.
입력
첫 번째 줄에 문자열 $X$가 주어진다.
출력
문자열 $X$를 $X$와 길이가 같으면서 KSAAC 운영진이 좋아하는 문자열로 바꾸기 위한 최소 시행 횟수를 출력한다.
제한
- $1\le |X|\le 5\times 10^5$
- $X_i \in \{$
K$,$S$,$A$\}$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $X$의 모든 문자가 동일 |
| 2 | 30 | $|X| \geq 3$; $X$는 |
| 3 | 60 | 추가 제약 조건 없음 |
예제 입력 1
KKSKASKA
예제 출력 1
8
출처
School > 한국과학영재학교 > 2024 KSA Automata Winter Contest B번
- 문제를 만든 사람: sooahn07
- 문제를 검수한 사람: hjroh0315, wizardrabbit, vkdldjvkdnj, utilforever, shiftpsh, parkky, naeby, mickeyjung, kiwiyou, jyheo98, hwpark12, aaron0526, gs22059, gs20036, flakepowders, eric00513, edward3378, dohoon, davidkim0, anchor, alex0211, ai4youej
채점 및 기타 정보
- 예제는 채점하지 않는다.