CF59C.Title
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Vasya has recently finished writing a book. Now he faces the problem of giving it the title. Vasya wants the title to be vague and mysterious for his book to be noticeable among others. That's why the title should be represented by a single word containing at least once each of the first k Latin letters and not containing any other ones. Also, the title should be a palindrome, that is it should be read similarly from the left to the right and from the right to the left.
Vasya has already composed the approximate variant of the title. You are given the title template s consisting of lowercase Latin letters and question marks. Your task is to replace all the question marks by lowercase Latin letters so that the resulting word satisfies the requirements, described above. Each question mark should be replaced by exactly one letter, it is not allowed to delete characters or add new ones to the template. If there are several suitable titles, choose the first in the alphabetical order, for Vasya's book to appear as early as possible in all the catalogues.
瓦西娅最近刚刚写完一本书。现在他面临着为这本书起书名的问题。瓦西娅希望书名含糊而神秘,以便使自己的书在众多书籍中脱颖而出。因此,书名必须是一个单词,其中至少包含前 k 个拉丁字母中的每一个,且不包含任何其他字母;此外,书名还必须是一个回文串,即从左到右读与从右到左读完全相同。
瓦西娅已经初步拟定了书名的模板。你将得到一个由小写拉丁字母和问号(?)组成的字符串 s 作为书名模板。你的任务是将所有问号替换为小写拉丁字母,使得最终得到的字符串满足上述全部要求。每个问号必须且只能被替换为一个字母,不允许删除或添加任何字符。如果存在多个满足条件的书名,请选择字典序最小的一个,以便瓦西娅的书在各类目录中尽可能靠前地出现。
输入格式
The first line contains an integer k (1 ≤ k ≤ 26) which is the number of allowed alphabet letters. The second line contains s which is the given template. In s only the first k lowercase letters of Latin alphabet and question marks can be present, the length of s is from 1 to 100 characters inclusively.
第一行包含一个整数 k(1≤k≤26),表示允许使用的字母数量。
第二行包含字符串 s,即给定的模板。在 s 中,仅可能出现拉丁字母表的前 k 个小写字母以及问号(?),s 的长度为 1 至 100 个字符(含端点)。
输出格式
If there is no solution, print IMPOSSIBLE. Otherwise, a single line should contain the required title, satisfying the given template. The title should be a palindrome and it can only contain the first k letters of the Latin alphabet. At that, each of those k letters must be present at least once. If there are several suitable titles, print the lexicographically minimal one.
The lexicographical comparison is performed by the standard < operator in modern programming languages. The line a is lexicographically smaller than the line b, if exists such an i (1 ≤ i ≤ |s|), that a__i < b__i, and for any j (1 ≤ j < i) a__j = b__j. |s| stands for the length of the given template.
若无解,输出 IMPOSSIBLE。否则,仅需在一行中输出满足给定模板的所需标题。该标题必须是回文串,且只能包含拉丁字母表的前 k 个字母。此外,这 k 个字母中的每一个都至少需出现一次。若存在多个满足条件的标题,请输出字典序最小的一个。
字典序比较采用现代编程语言中的标准 < 运算符。字符串 a 的字典序小于字符串 b,当且仅当存在某个下标 i(1 ≤ i ≤ ∣s∣),使得 ai < bi,且对任意 j(1 ≤ j < i)均有 aj = bj。其中 ∣s∣ 表示给定模板的长度。
输入输出样例
输入#1
3 a?c
输出#1
IMPOSSIBLE
输入#2
2 a??a
输出#2
abba
输入#3
2 ?b?a
输出#3
abba
输入解题思路,AI测评打分。不知道怎么写?