実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
高橋くんは、すぬけくんに日頃の感謝を込めてレベル K の回文を送ることにしました。レベル L の回文 ( L は 0 以上の整数 ) は以下のように定義されます。
- 文字列 s の左右を反転させたものを \mathrm{rev}(s) と表す。
- 文字列 s は s = \mathrm{rev}(s) であるとき、回文という。
- 空文字列と回文でない文字列はレベル 0 の回文である。
- 任意の空でないレベル L - 1 の回文 t に対して、t, \mathrm{rev}(t) をこの順に繋げた文字列はレベル L の回文である。
- 任意のレベル L - 1 の回文 t と任意の文字 c に対して、t, c, \mathrm{rev}(t) をこの順に繋げた文字列はレベル L の回文である。
いま、高橋くんは文字列 S を持っています。
S から 1 文字選んで別の英小文字に書き換えるということを 0 回以上繰り返すことで、S をちょうどレベル K の回文にすることができるか判定してください。また、できる場合は、S がちょうどレベル K の回文になるまでに必要な最小の書き換え回数を求めてください。
制約
- K は整数
- 0 ≤ K ≤ 5 \times 10^5
- S は英小文字からなる
- 1 ≤ |S| ≤ 5 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
K S
出力
ちょうどレベル K の回文を作ることができる場合は、必要な最小の書き換え回数を出力せよ。
できない場合は、impossible
と出力せよ。
入力例 1
4 aabaaaabaa
出力例 1
0
aabaaaabaa
のレベルは以下のように計算できます。
- 空文字列はレベル 0 の回文である。
a
は (空文字列),a
, (空文字列) を順に繋げた文字列だから、レベル 1 の回文である。aa
はa
,a
を順に繋げた文字列だから、レベル 2 の回文である。aabaa
はaa
,b
,aa
を順に繋げた文字列だから、レベル 3 の回文である。aabaaaabaa
はaabaa
,aabaa
を順に繋げた文字列だから、レベル 4 の回文である。
よって、aabaaaabaa
は初めからレベル 4 の回文であるので、書き換える必要はありません。
入力例 2
2 aabaaaabaa
出力例 2
4
例えば、aabaaaabaa
を acbcaacbca
に書き換えると、ちょうどレベル 2 の回文を作ることができます。
aabaaaabaa
はレベル 2 の回文ではないことに注意してください。
入力例 3
3 aabaaaabaa
出力例 3
impossible
入力例 4
5 aabaaaabaa
出力例 4
impossible
入力例 5
2 acaabcbababaaac
出力例 5
6
Score : 500 points
Problem Statement
As a token of his gratitude, Takahashi has decided to give Snuke a level-K palindrome. A level-L palindrome, where L is a non-negative integer, is defined as follows:
- Let \mathrm{rev}(s) denote the reversal of a string s.
- A string s is said to be a palindrome when s = \mathrm{rev}(s).
- The empty string and a string that is not a palindrome are level-0 palindromes.
- For any non-empty level-(L-1) palindrome t, the concatenation of t, \mathrm{rev}(t) in this order is a level-L palindrome.
- For any level-(L-1) palindrome t and any character c, the concatenation of t, c, \mathrm{rev}(t) in this order is a level-L palindrome.
Now, Takahashi has a string S. Determine whether it is possible to make S an exactly level-K palindrome by doing the following action zero or more times: choose a character in S and change it to another lowercase English letter. If it is possible, find the minimum number of changes needed to make S a level-K palindrome.
Constraints
- K is an integer.
- 0 ≤ K ≤ 5 \times 10^5
- S consists of lowercase English letters.
- 1 ≤ |S| ≤ 5 \times 10^5
Input
Input is given from Standard Input in the following format:
K S
Output
If it is possible to get an exactly level-K palindrome, print the minimum number of changes needed.
If it is impossible, print impossible
.
Sample Input 1
4 aabaaaabaa
Sample Output 1
0
We can find the level of aabaaaabaa
as follows:
- the empty string is a level-0 palindrome;
a
is a concatenation of (empty string),a
, (empty string) in this order, so it is a level-1 palindrome;aa
is a concatenation ofa
,a
in this order, so it is a level-2 palindrome;aabaa
is a concatenation ofaa
,b
,aa
in this order, so it is a level-3 palindrome;aabaaaabaa
is a concatenation ofaabaa
,aabaa
in this order, so it is a level-4 palindrome.
Thus, aabaaaabaa
is already a level-4 palindrome and needs no changes.
Sample Input 2
2 aabaaaabaa
Sample Output 2
4
We can, for example, change aabaaaabaa
to acbcaacbca
to get a level-2 palindrome.
Note that aabaaaabaa
is not a level-2 palindrome.
Sample Input 3
3 aabaaaabaa
Sample Output 3
impossible
Sample Input 4
5 aabaaaabaa
Sample Output 4
impossible
Sample Input 5
2 acaabcbababaaac
Sample Output 5
6