시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 116 40 26 26.804%

문제

영선이는 팰린드롬을 너무 좋아한다. 따라서 영선이의 이상형은 팰린드롬을 좋아하는 사람이다. 하지만 안타깝게도 영선이는 이상형을 찾을 수 없었다! 

 모든 것이 너무 완벽한 자신 때문에 이상형 찾을 수 없다고 생각한 영선이는 자신의 완벽함을 줄이기로 했다. 따라서 이제 영선이의 이상형은 완벽한 팰린드롬을 좋아할 필요가 없다. 영선이의 이상형이 θ(0 < θ ≤ 1, θ는 실수) 값보다 큰 유사 팰린드롬을 좋아해도 상관 없는 것이다. 편의상 θ값보다 큰 유사 팰린드롬을 θ-팰린드롬이라 하자. θ-팰린드롬이 되기 위한 조건은 다음과 같다.

  1. 어떤 문자열 w는 반드시 uvuR꼴을 만족해야한다. (uR은 u를 반대로 뒤집은 것을 말한다. u=ab라면 uR=ba)
  2. v는 빈 문자열이 될 수 있으나 u는 빈 문자열이 될 수 없다.
  3. θ ≤ 2|u|/|w|식을 만족해야한다.(|s|는 문자열의 길이를 의미)

  예를들어 θ 가 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

예제 입력 2

7 3 5
abbaaba

예제 출력 2

2

예제 입력 3

7 4 5
abcdefg

예제 출력 3

0

힌트