Лабораторная работа № 3. Комбинаторика.

Цель: Научиться решать задачи по программированию с использованием правил комбинаторики.

Общее количество баллов на лабораторную работу – 20 баллов

ЗАДАНИЯ.

Задача 1. Подстановочный шифр 5 баллов

Шифрование строки подстановочным шифром производится путём замены каждого символа алфавита на другой символ. Разумеется, для однозначного шифрования и дешифрования необходимо, чтобы каждому символу исходного алфавита соответствовал ровно один символ зашифрованного, и наоборот. Например, при помощи шифра М  А, А  R, Y  К слово МАYА будет зашифровано в АRKR.

Даны две строки одинаковой длины, состоящие из заглавных латинских букв. Требуется найти подстановочный шифр, при помощи которого первая строка шифруется во вторую, или определить, что такого не существует. Например, для слов «GOOD» и «WELL» шифра не существует, потому что, с одной стороны буква «О» преобразуется одновременно в «E» и «L», а с другой стороны, буквы «О» и «D» обе превращаются в «L».

Формат входного и выходного файлов

Входной файл содержит две строки не более 50 символов длиной. Выходной файл должен содержать последовательность пар символов, обозначающих замену при шифровании первого символа пары на второй. Пары должны быть расположены по одной в строке и отсортированы по алфавиту.

В случае если шифра не существует, следует вывести в выходной файл строку «--» (два знака минус).

Пример файла INPUT.ТХТ: MAYA ARKR	Соответствующий OUTPUT.ТХТ: AR MA YK
TRAINING TAADFTFK	– –

Задача 2. Длинный отрезок 5 баллов

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

Формат входного и выходного файлов

В первой строке входного файла содержится число вершин N (4  N  50). В следующих строках расположены целочисленные координаты вершин х_i, у_i (1  х_i, у_i  1000), перечисленные в порядке обхода. (При этом у каждой пары соседних вершин либо координаты х, либо координаты y совпадают).

Выходной файл должен содержать единственное целое число — длину самого длинного отрезка.

Пример файла INPUT.ТХТ: 8 15 10 20 10 20 20 40 20 40 5 60 5 60 50 15 50	Соответствующий OUTPUT.ТХТ: 45
8 10 50 20 50 20 0 30 0 30 60 20 60 20 80 10 80	80

Задача 3. Миллион Z 8 баллов

Дана строка, состоящая из одного миллиона букв «Z». Определим операцию замены, которая характеризуется тремя параметрами (, i, j) и состоит в замене на букву  букв строки начиная с позиции i до позиции j. Требуется определить, сколько различных букв будет в строке после выполнения заданной последовательности операций замены.

Формат входного и выходного файлов

В первой строке входного файла содержится число замен N (0  N  1000). В следующих N строках содержатся тройки  i j, где  — заглавная латинская буква, i и j — целые числа (1  i  i j  10⁶).

Выходной файл должен содержать единственное целое число — количество различных букв в результирующей строке.

Пример файла INPUT.ТХТ: 3 А 1 50 Х 90 1000 D 30 1000000

Соответствующий OUTPUT.ТХТ: 2

Задача 4. Семикратные подчисла

В данной строке, состоящей из цифр от 0 до 9 найти подстроку, представляющую запись числа, неравного нулю и кратного семи.

Например, в строке 560005672 есть подходящие подстроки— 7, 56, 560, 672 и т.д.

Формат входного и выходного файлов

Во входном файле содержится строка длиной от 1 до 1000. Выходной файл должен содержать число 1, если хотя бы одна такая подстрока найдена, и число 0 в противном случае.

Пример файла INPUT.ТХТ: 560005672	Соответствующий OUTPUT.ТХТ: 1
100	0

Задача 5. Маршрутка 10 баллов

Маршрутное такси на Р посадочных мест движется по линии с N остановками, пронумерованными от 1 до N в порядке следования такси. На остановках стоят очереди из пассажиров, каждый из которых желает попасть на некоторую остановку, расположенную дальше по маршруту. Водитель забирает на первой остановке f пассажиров и отправляется в путь. На каждой следующей остановке выходят все пассажиры, желавшие на неё попасть. Затем пассажиры садятся в порядке очереди до тех пор, пока не заполнится такси или не закончится очередь.

Каждый пассажир платит водителю 5 рублей.

Требуется определить при каком значении f (возможно, нулевом), доход водителя будет наибольшим и вывести этот доход.