Районная олимпиада по информатике 2005-2006 учебного года

Задача 1. Шифровка с помощью ключевого слова (30 баллов).

Кодирование сообщения производится с помощью ключевого слова следующим образом:

Строится таблица размером n*m, n – количество букв в ключевом слове, m – количество строк, достаточных для размещения сообщения в таблице.
Записывается в каждую клетку таблицы по одной букве сообщения слева направо и сверху вниз. В пустые ячейки последней строки таблицы (если есть) запишем «ъ».
Столбцы таблицы нумеруются в соответствии с порядком, в котором встречаются буквы ключевого слова в алфавите.
Буквы выписываются подряд по столбцам сверху вниз, начиная со столбца, отмеченного числом 1, затем столбца помеченного числом 2 и т.д.

Задание

1. По заданному сообщению и ключевому слову получить шифровку.

2. По заданному зашифрованному сообщению и ключевому слову получить исходное сообщение.

Формат входных данных

Текстовый файл входных данных INPUTn.TXT содержит:

в первой строке число 1, если выполняется задание 1 или 2 если выполняется задание 2

во второй строке ключевое слово

в третьей строке сообщение

Формат выходных данных

В выходной текстовый файл OUTPUTn.TXT вывести результат.
Предусмотреть вывод результата на экран.

Задача 2. Ломаная линия (25 баллов)

На клетчатой бумаге нарисован квадрат размером n на n клеток. Из левого нижнего угла квадрата проводится ломаная линия. Каждое звено ломаной параллельно какой-либо стороне квадрата. Звенья с нечетными номерами горизонтальны, с четными — вертикальны. Вершины ломаной линии совпадают с углами клеток, а вся ломаная линия не должна выходить за пределы квадрата.

Проведенная ломаная линия задается последовательностью целых чисел. Каждое число характеризует одно звено ломаной и по модулю равно длине звена. При этом для горизонтальных звеньев направление вправо при рисовании ломаной задается положительными числами, а направление влево — отрицательными числами; для вертикальных звеньев положительное направление — это направление вверх, а отрицательное — вниз. Будем говорить, что ломаная имеет самопересечения, если найдется хотя бы одна точка, принадлежащая одновременно двум различным звеньям, либо найдутся две совпадающие вершины.

Пусть заданы n — размер квадрата, m — количество звеньев и L₁ , L₂ , …, L_m — числовая последовательность, описывающая ломаную. Проверить, не выходит ли ломаная за пределы квадрата и имеет ли ломаная самопересечения.

Текстовый файл INPUTn.TXT содержит в первой строке два целых числа: n — сторона квадрата (1 £ n £ 20), m — количество звеньев ломаной линии (1 £ m £ 500). Далее следуют m целых ненулевых чисел. Числа разделяются одним или несколькими пробелами и/или признаком конца строки. Эти числа задают длины и направления отдельных звеньев.

    В текстовый файл OUTPUTn.TXT вывести сообщение:
    · “ошибка”, если ломаная выходит за пределы квадрата;
    · “да”, если ломаная не выходит за пределы квадрата и имеет самопересечения;
    · “нет”, если ломаная не выходит за пределы квадрата и не имеет самопересечений.

Задача 3. Города (45 баллов)

Называется какой-нибудь город, допустим, "САРАТОВ". Название заканчивается на "В", значит требуется назвать другой город, у которого в названии первая буква "В". Это может быть "ВОРОНЕЖ". Следующий город должен начинаться на "Ж" и т.д. Название города не может начинаться с буквы «Ь». В этом случае следующее название города должно начинаться с предпоследней буквы.

Надо написать программу, которая из набора названий городов (все названия разные) строит цепочку максимальной длины.

файл INPUTn.TXT в 1-й строке содержит количество названий городов в наборе (не превышает 20).

Начиная со второй строки (по одному в строке) следуют названия городов (все буквы в названиях городов заглавные).

1-я строка OUTPUTn.TXT содержит длину максимальной цепочки. Начиная со второй строки идет вариант цепочки, т.е. названия (по одному в строке) городов в порядке, который требуют условия игры.