← 返回题目列表

AtCoder · jsc2021_e

E. K 级回文

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

为了表达谢意,高桥决定给Snuke一个等级——K 回文。 A级——L 回文,其中 L 是一个非负整数,定义如下:

  • 让 \mathrm{rev}(s) 表示字符串的反转 当 s.
  • 一个字符串 s 被认为是回文时 s = \mathrm{rev}(s).
  • 空字符串和非回文字符串是 level-0 回文。
  • 对于任何 非空 级别-(L-1) 回文 t,串联 t, \mathrm{rev}(t) 按此顺序是一个级别-L 回文。
  • 对于任何级别-(L-1) 回文 t 和任何字符 c,串联 t, c, \mathrm{rev}(t) 按此顺序是一个级别-L 回文。

现在,高桥有一根绳子 S。 判断是否可以制作 S 完全水平-K 回文通过执行以下操作零次或多次:选择一个字符 S 并更改为另一个小写英文字母。如果可能的话,找出需要进行的最少更改次数 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 to acbcaacbca 获得等级-2 回文。

请注意 aabaaaabaa 不是一个级别-2 回文。


示例输入 3

3
aabaaaabaa

示例输出 3

impossible

示例输入 4

5
aabaaaabaa

示例输出 4

impossible

示例输入 5

2
acaabcbababaaac

示例输出 5

6