시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 756 | 201 | 143 | 31.429% |
영선이는 팰린드롬을 너무 좋아한다. 따라서 영선이의 이상형은 팰린드롬을 좋아하는 사람이다. 하지만 안타깝게도 영선이는 이상형을 찾을 수 없었다!
모든 것이 너무 완벽한 자신 때문에 이상형 찾을 수 없다고 생각한 영선이는 자신의 완벽함을 줄이기로 했다. 따라서 이제 영선이의 이상형은 완벽한 팰린드롬을 좋아할 필요가 없다. 영선이의 이상형이 θ(0 < θ ≤ 1, θ는 실수) 값보다 큰 유사 팰린드롬을 좋아해도 상관 없는 것이다. 편의상 θ값보다 큰 유사 팰린드롬을 θ-팰린드롬이라 하자. θ-팰린드롬이 되기 위한 조건은 다음과 같다.
예를들어 θ 가 0.8이고 w =ababa라고 하자. w는 θ-팰린드롬이라 할 수 있는데 u = ab, v = a로 설정할 경우 θ ≤ 2|u|/|w|를 만족하기 때문이다. (0.8 ≤ 2*2/5)
영선이는 이 정도면 이상형을 찾을 수 있을 것이라고 생각하고 길거리로 나가 이상형을 찾았다. 영선이는 사람들에게 가장 좋아하는 문자열을 요청했고, 안타깝게도 그 문자열들은 모두 θ-팰린드롬을 만족하지 못했다! 영선이는 좌절하지 않고 조건을 더 완화하기로 했다. 이제 영선이의 이상형은 꼭 θ-팰린드롬을 좋아할 필요가 없다. θ-팰린드롬들을 이어 붙인 문자열을 좋아해도 된다. 하지만 이왕이면 적은 숫자의 θ-팰린드롬을 이어 붙인 문자열을 더 좋아한다.
예를들면 θ가 0.5고 w=abbaaba라고 가정해보자. 이 문자열은 자체적으로 θ-팰린드롬이다. u =ab,v=baa라면 θ ≤ 2|u|/|w|=4/7 이기 때문이다. 반면 θ가 0.6이라 하자. 이 문자열 자체로 θ-팰린드롬은 아니다. 하지만 θ-팰린드롬인 abba와 aba를 붙이면 abbaaba가 되므로 이 문자열을 제시한 사람은 영선이의 이상형이다. 따라서 영선이가 고백을 할 것이다!
하지만 문제가 생겼다. 어떤 사람이 문자열을 제시했을 때 그것이 θ-팰린드롬인지를 확인하는 것은 쉬웠지만 θ-팰린드롬을 붙여서 만들 수 있는 문자열인지 아닌지를 파악하기는 어려웠던 것이다. 이 문제를 해결하기 위해 영선이가 어려분에게 도움을 요청했다. 여러분이 영선이가 연애를 할 수 있도록 도와주자. 사람들의 문자열 w를 제시하고 영선이의 기준인 θ값이 주어질 때, w를 가장 적은 수의 θ-팰린드롬으로 구성했을 때의 개수를 출력하는 프로그램을 작성하시오.
입력은 2개의 줄로 구성된다.
첫 번째 줄은 3개의 정수 n,k,l(1 ≤ n ≤ 10,000, 1 ≤ k ≤ l ≤ 100)이 주어진다. 이때 n은 사람들이 제시한 문자열 w의 길이, θ = k/l이다.
그 다음 줄에는 문자열 w가 소문자로 주어진다.
w를 구성할 수 있는 가장 적은 숫자의 θ-팰린드롬의 개수를 출력하시오.
만약 θ-팰린드롬으로 구성할 수 없는 문자열이라면 0을 출력하시오.
7 1 2 abbaaba
1
7 3 5 abbaaba
2
7 4 5 abcdefg
0
ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2016 F번