eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Схований код

Схований код

Настав час перевірити Ваші хакерські здібності! У Вас попросили допомоги зламати коди ворога в поточній війні з ... або кимось іншим. У всякому разі, Вам слід розкрити техніку шифрування, використовувану супротивником. Це досить просто, і відбувається наступним чином. Відзначимо, що всі рядки містять тільки великі літери латинського алфавіту. \begin{enumerate} \item Є ключ \textbf{K} та відкритий текст \textbf{P}. Він закодований посимвольно, в результаті чого отримано шифр \textbf{C} такої ж довжини. \item Позначимо через |\textbf{K}| довжину ключа \textbf{K}. Тоді перші |\textbf{K}| символів \textbf{C} отримані додаванням перших |\textbf{K}| символів \textbf{P} до символів \textbf{K}. Під додаванням двох символів мається ну увазі їх інтерпретація як чисел (\textbf{A = 0}, \textbf{B = 1} і так далі) та взяття суми за модулем \textbf{26}. Тобто \textbf{C_i = (P_i + K_i ) mod 26} для \textbf{i = 1, ... ,|K|}. Якщо |\textbf{K}| > |\textbf{P}|, то зайві символи \textbf{K} ігноруються. \item Решта символів \textbf{P}, тобто \textbf{P_i} для \textbf{i} > |\textbf{K}|, кодуються з використанням попередніх символів шифротексту за формулою \textbf{C_i = (P_i + C_\{i−|K|\}) mod 26} для \textbf{i = |K| + 1, ..., |P|}. \end{enumerate} Наприклад, розглянемо шифрування рядка "\textbf{STANFORD}" ключем "\textbf{ACM}": \textbf{STA NFORD + ACM SVMFA ---------- SVM FAAWD} Знаючи алгоритм, Вам необхідно прочитати повідомлення ворога. На щастя, у Вас є декілька відкритих текстів та відповідних їм шіфротекстів, здобутих Вашою командою. Відомо, що всі вони зашифровані одним і тим же ключем. Допоможіть знайти ключ, яким користувався супротивник. \InputFile Складається з декількох тестів. Кожний тест починається з рядка, що містить кількість \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100}) відомих Вам пар текст - шифротекст. Кожний з наступних \textbf{n} рядків містить два рядки \textbf{P} та \textbf{C} - текст та шифротекст відповідно. \textbf{P} та \textbf{C} містять лише заголовні літери (\textbf{A}-\textbf{Z}) та мають однакову довжину (не більш ніж \textbf{100} символів). Останній рядок містить \textbf{n = 0} та не обробляється. \OutputFile Для кожного тесту в окремому рядку вивести найкоротший можливий ключ, або "\textbf{Impossible}", якщо такого ключа не існує.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
1
A B
3
STANFORD SVMFAAWD
AVOWIENR AXAWFEJW
VAMRI VCYMK
3
ABCDEFGHIJKLMNOPQRSTUVWXYZ AAAAAAAAAAAAAAAAAAAAAAAAAA
Y Y
Z Z
2
A B
B A
0
Вихідні дані #1
B
ACM
AZYXWVUTSRQPONMLKJIHGFEDCB
Impossible
Джерело 2011 Stanford Local ACM Programming Contest, Saturday, October 8th, 2011