← 返回题目列表

Codeforces · 137/D

D. 回文

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

星期五是波利卡普斯一周中最喜欢的一天。不是因为接下来是周末,而是因为周五的课程是 2 节 IT 课、2 节数学课和 2 节文学课。当然,波利卡帕斯已经为所有人做好了准备,这与他的好友因诺森提乌斯不同。 Innocentius整个晚上都在玩他最喜欢的游戏Fur2,没有足够的时间来做文学任务。由于Innocentius不想得F,他决定完成这项任务,并在IT和数学课上读了一本名为《风暴与平静》的书(他以前在这些科目上从来没有遇到过问题)。当 IT 老师 Watkins 先生看到这一情况时,他决定给 Innocentius 布置另一项任务,让这个男孩更多地专注于课程,而不是专注于与 IT 无关的工作人员。

沃特金斯先生说,回文是一个可以在任一方向以相同方式读取的字符串,从左到右和从右到左。字符串 a、b 的串联是字符串 ab,是字符串 b 与字符串 a 连续相加的结果。当然,伊诺琴蒂斯知道这一切,但任务比他想象的要困难得多。沃特金斯先生要求更改《暴风雨与平静》中的最小字符数,以便该书的文本也将是不超过 k 个回文的串联。因诺森提斯无法完成任务,因此要求你帮助他。

输入

第一输入行包含一个非空字符串 s,它是“Storm and Calm”的文本(不带空格)。字符串s的长度不超过500个字符。字符串 s 由大写和小写拉丁字母组成。第二行包含单个数字 k(1 ≤ k ≤ |s|,其中 |s| 表示字符串 s 的长度)。

输出

在第一行打印 Innocentius 必须进行的最少更改数。在第二行打印由不超过 k 个回文组成的字符串。每个回文应该是非空的,并且由大写和小写拉丁字母组成。使用字符“+”(ASCII 代码 43)分隔连续的回文。如果存在多个解决方案,请打印其中任何一个。

字母的大小写确实很重要,即大写字母不被视为等同于相应的小写字母。

示例

输入 #1

abacaba
1

输出 #1

0
abacaba

输入 #2

abdcaba
2

输出 #2

1
abdcdba

输入 #3

abdcaba
5

输出 #3

0
a+b+d+c+aba

输入#4

abacababababbcbabcd
3

输出#4

1
abacaba+babab+bcbabcb