Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
267. Послание к инопланетянам
Олимпиадные задачи на русском языке| 02/07/2007 | Лето 2007 дорешивание (10F) |
| 23/07/2007 | Лето 2007 - 10 (F) |
| 25/10/2008 | Занятие 6 (E) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Программист Вася хочет отправить послание длины `k`
к инопланетянам. Для этого он взял текст
одной из своих
любимых песен, и хочет в него вставить пробелы таким образом, чтобы строчка, составленная
из `n`-го, `2n`-го, …, `"kn"`-го символа образовывала заданное послание (`(k+1)n`-й и
дальнейшие символы не входят в послание). Пробелы можно вставлять только на тех
местах, где уже встречается хотя бы один пробел.
Все символы с кодом 13 (CR) во входном файле игнорируются, а символ с кодом
10 (LF) считается эквивалентным символу с кодом 32 (пробелу). Таким образом,
один перевод строки во всей задаче считается полностью эквивалентным одному
пробелу.
Естественно, так как каждый символ, отправляемый инопланетянам, стоит денег, то Вася
хочет отправить послание минимально возможной длины (перевод строки
опять же считается одним символом, так как на посылающей
машине стоит UNIX). Как ему это сделать?
В первой строке входного файла содержится натуральное число `n`, меньшее 250. Во второй
строке содержится послание, которое должно быть закодировано. Начиная с третьей строки
идет сам текст песни, содержащий только символы с кодами 32..255, а также последовательности
из двух символов 13 10 (т.е. перевод строки), считающиеся эквивалентными одному пробелу.
Длина текста песни не превосходит 1000 символов
(перевод строки считается за один символ), а длина послания — 50 символов.
Послание может содержать пробелы, но не переводы строки (при этом разрешается
сопоставить пробелу в послании перевод строки в тексте).
Символы, отличающиеся регистром написания, считаются различными.
В первой строке выходного файла выведите минимально возможное число вставляемых
пробелов. Начиная со второй строки, необходимо вывести текст минимальной длины
со вставленными пробелами, в котором можно прочитать заданное послание.
Переводы строки рассматриваются проверяющей программой аналогично правилам, применимым ко входному
файлу (один перевод строки считается эквивалентным одному пробелу).
Если в текст песни невозможно вставить пробелы таким образом, то выведите в выходной
файл единственное слово "IMPOSSIBLE".
Для удобства в примере все пробелы заменены на звездочки. Ваше решение должно
выводить настоящие пробелы (то есть символы с кодом 32)!
Пример ввода
18 привет Уронили мишку на пол, Оторвали мишке лапу, Все равно его не брошу, Потому что он хороший!
Пример вывода
32 Уронили*мишку*на*пол,********** Оторвали************мишке**лапу, Все*равно**********его*не**брошу, Потому*что*он*хороший!
