Программирование. Олимпиадное программирование. Есть строка, неизвестные символы заменены на ?. нужно расшифровать.
Условие достаточно большое, но сам смысл задачи достаточно простой. На вход подается строка и кол-во символов, неизвестные символы заменены на "?". Так же там есть "_", они не могут стоять подряд и строка не может начинаться с них. Нужно сделать так, чтобы все буквы английского алфавита были использованы и были соблюдены условия, которые сказаны выше. Если так сделать нельзя, то вывод -1. Ниже я привёл текст задачи, но я сверху я "выжал" из него все условия.
Пример:
35
mr_jock_tv_quiz_phd_bags_few_lyn???
Вывод: -1 (тут вывелось -1 т.к. все символы алфавита уже использовались, но есть три стоящих подряд ?)
В голову не приходит какие ещё условия могут быть и как именно заменять знаки вопроса.
В далёкой-далёкой галактике повстанцы проводят испытания новой системы передачи
закодированных сообщений, недоступной агентам Императора.
Для проверки систем приёма и передачи закодированных сообщений часто используются
фразы-панграммы (то есть фразы, содержащие все буквы латинского алфавита). Если
фраза при этом не содержит никакую букву более, чем один раз, то такая фраза
называется идеальной панграммой. Для испытаний этой системы была взята идеальная
панграмма из нескольких слов. Слова разделены знаками ‘”. При этом соблюдаются
стандартные полиграфические правила, для разделителей — фраза не может ни начинаться,
ни заканчиваться разделителем, ни содержать двух разделителей подряд.
к сожалению, первый эксперимент прошёл не вполне удачно — часть символов в полученном
сообщении распознать не удалось (но известно, что каждый нераспознанный объект является
одним символом или пробелом, тем самым известна длина сообщения).
Ваша задача — по полученному сообщению восстановить нераспознанные объекты так, чтобы
переданный текст соответствовал описанию (то есть был идеальной панграммой, в которой
при наличии разделителей соблюдаются стандартные полиграфические правила).
Формат входных данных
Первая строка входных данных содержит одно целое число и, — длину строки (1 <п < 60).
Вторая строка содержит полученный текст — строку длины п, состоящую из строчных
латинских букв, знаков подчёркивания (‘_’), разделяющих слова, и знаков вопроса —
нераспознанных символов. Гарантируется, что во входных данных подчёркивание не
является ни первым, ни последним символом, а также что во входных данных отсутствуют
два подчёркивания подряд.
Формат выходных данных
Если переданная строка не могла быть идеальной панграммой, не начинающейся и не
заканчивающейся подчёркиванием и не содержащей двух подчёркиваний подряд, выведите
—1. В противном случае выведите вариант расшифровки нераспознанных символов,
при котором строка является идеальной панграммой, не начинается и не заканчивается
подчёркиванием и не содержит двух подчёркиваний подряд. Если вариантов несколько,
выведите любой.
В данной задаче нужно составить строку, удовлетворяющую следующим условиям:
– Строка содержит определенное количество символов (задано первым числом на входе).
– В строке есть подстрока “mr_jock_tv_quiz_phd_bags_few_lyn” (это условие можно учесть, просто не используя данные символы при составлении строки).
– Буквы английского алфавита в строке не повторяются.
– Не допускается подряд два символа “”.
– Строка не может начинаться с символа “”.
Если все буквы английского алфавита использованы и при этом выполнены все условия, то выводим полученную строку. Если невозможно составить строку, не нарушающую условия, выводим -1.
Составляя строку, следует учесть, что количество символов в строке фиксировано, поэтому нужно использовать все доступные символы, чтобы не нарушать условие об отсутствии повторений. Также следует избегать использования символов “_” в начале строки и двух подряд.
Ниже представлен возможный алгоритм решения данной задачи:
1. Считать количество символов и подстроку “mr_jock_tv_quiz_phd_bags_few_lyn”, которую нужно исключить.
<есть три стоящих подряд >
вероятно это пробелы (код символа = 32)