Арне Сакнуссемм
Следуя сюжету Жюля Верна, зашифрованное сообщение, созданное средневековым алхимиком Арне Сакнуссемом и расшифрованное профессором Лиденброком, стало началом невероятного путешествия к центру Земли. Процесс шифрования, который использовал Арне, описан ниже.
1. Возьмите непустое сообщение M, содержащее буквы английского алфавита, цифры, запятые, точки, кавычки, пробелы и строки, при этом последний символ не является пробелом. Например, рассмотрим следующее сообщение, перевод которого звучит как "В кратере Снеффельса спускайся, смелый путешественник, и коснись центра Земли".
In Sneffels craterem descende audasviator, et terrestre centrum attinges.
2. Выберите целое число K и добавьте пробелы в конце M так, чтобы длина полученного сообщения, назовем его M', была наименьшим кратным K. Для K=19 и приведенного выше сообщения, где длина M равна 74 (включая 8 пробелов и строку, которые содержит M), добавляются два пробела в конце, что дает сообщение M' с длиной 76.
3. Замените все пробелы в M' на символ подчеркивания (_); замените все строки в M' на обратный слеш (), а затем переверните сообщение. В нашем случае:
__.segnitta_murtnec_ertserret_te_,rotaiv\sadua_ednecsed_meretarc_sleffenS_nI
4. Запишите сообщение, полученное на шаге 3, в таблицу с length(M')/K строками и K столбцами. Запись ведется по столбцам. Для данного примера сообщение записывается в таблицу с 76/19=4 строками и 19 столбцами следующим образом:
5. Строки символов, соответствующие строкам таблицы, являются фрагментами зашифрованного сообщения. Четыре фрагмента сообщения Арне, приведенные на шаге 1, являются:
Напишите программу, которая расшифровывает непустые сообщения, зашифрованные, как описано. Длина сообщения до шифрования составляет не более 1000 символов, включая пробелы и строки.
Входные данные
Вход программы осуществляется из текстового файла, где каждый набор данных соответствует зашифрованному сообщению. Набор данных начинается с целого числа n, которое показывает количество фрагментов зашифрованного сообщения, и продолжается n строками символов, которые обозначают фрагменты, в порядке, в котором они появляются в таблице с шага 4 процедуры шифрования. Входные данные разделены пробелами и заканчиваются концом файла.
Выходные данные
Расшифрованное сообщение должно быть напечатано на стандартный выход, начиная с новой строки и должно быть отделено пустой строкой, как показано в образце ввода/вывода ниже.