Лабораторная работа № 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.ТХТ: 15 10 20 10 20 20 40 20 40 5 60 5 60 50 15 50 | Соответствующий OUTPUT.ТХТ: |
| 10 50 20 50 20 0 30 0 30 60 20 60 20 80 10 80 |
Задача 3. Миллион Z 8 баллов
Дана строка, состоящая из одного миллиона букв «Z». Определим операцию замены, которая характеризуется тремя параметрами (a, i, j) и состоит в замене на букву a букв строки начиная с позиции i до позиции j. Требуется определить, сколько различных букв будет в строке после выполнения заданной последовательности операций замены.
Формат входного и выходного файлов
В первой строке входного файла содержится число замен N (0 £ N £ 1000). В следующих N строках содержатся тройки a i j, где a — заглавная латинская буква, i и j — целые числа (1£ i £ i j £ 106).
Выходной файл должен содержать единственное целое число — количество различных букв в результирующей строке.
| Пример файла INPUT.ТХТ: А 1 50 Х 90 1000 D 30 1000000 | Соответствующий OUTPUT.ТХТ: |
Задача 4. Семикратные подчисла
В данной строке, состоящей из цифр от 0 до 9 найти подстроку, представляющую запись числа, неравного нулю и кратного семи.
Например, в строке 560005672 есть подходящие подстроки— 7, 56, 560, 672 и т.д.
Формат входного и выходного файлов
Во входном файле содержится строка длиной от 1 до 1000. Выходной файл должен содержать число 1, если хотя бы одна такая подстрока найдена, и число 0 в противном случае.
| Пример файла INPUT.ТХТ: | Соответствующий OUTPUT.ТХТ: |
Задача 5.Маршрутка 10 баллов
Маршрутное такси на Р посадочных мест движется по линии с N остановками, пронумерованными от 1 до N в порядке следования такси. На остановках стоят очереди из пассажиров, каждый из которых желает попасть на некоторую остановку, расположенную дальше по маршруту. Водитель забирает на первой остановке f пассажиров и отправляется в путь. На каждой следующей остановке выходят все пассажиры, желавшие на неё попасть. Затем пассажиры садятся в порядке очереди до тех пор, пока не заполнится такси или не закончится очередь.
Каждый пассажир платит водителю 5 рублей.
Требуется определить при каком значении f (возможно, нулевом), доход водителя будет наибольшим и вывести этот доход.
Формат входного и выходного файлов
В первой строке входного файла содержатся числа N и Р (2 £ N £ 50, 1 £ Р £ 20). В следующих N- 1 строках находятся чиста Кi di, 1… di,Ki (0 £ Кi £ Р, i £ di,j £ N) — количество пассажиров на очередной остановке и цель каждого пассажира. (На конечной остановке пассажиры не садятся).
Выходной файл должен содержать единственное целое число— максимальный доход водителя в рублях.
| Пример файла INPUT.ТХТ: 4 3 2 2 4 3 3 3 3 2 4 4 | Соответствующий OUTPUT.ТХТ: |
Задача 5. «Волшебное зелье» 10 баллов. При составлении волшебных зелий Северус Снегг заставляет учеников заучивать все рецепты. Но однажды Рон Уизли не приготовил домашнее задание и не может приготовить смесь. Верная Гермиона передала Гарри Поттеру шпаргалку, на которой записаны названия элементов, входящих в рецепт. Но необходимо знать, в каком порядке их следует смешивать. И вот теперь Гарри пытается перебрать различные варианты смешивания, чтобы выручить Рона.
Помогите Гарри получить все возможные варианты приготовления зелья.
Формат входных данных:
В первой строке входного файла записано целое число: N – количество составных элементов требуемой смеси. В следующих N строках записаны названия элементов. (0<N<=100)
Формат выходных данных:
Выходной файл должен содержать перечень всех возможных вариантов смешивания по одному варианту в строке. Для вывода будем считать, что составные элементы пронумерованы в том порядке, в каком они записаны во входном файле. Вариант смешивания задается перечнем номеров исходных элементов, записанных через пробел. Варианты могут быть выведены в произвольном порядке.
Пример:
| INPUT.TXT | OUTPUT.TXT |
| сера пепел растертый зуб вампира | 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 |
Задача 6. «Волшебная химия» 10 баллов. Злобный Северус Снегг часто проводит контрольные работы. На последней проверке он дал такое задание: дано N различных магических веществ, необходимо получить все возможные смеси этих веществ. Для составления смесей не обязательно использовать все исходные вещества.
Обозначая вещество его номером так, как это было проделано в задаче 5, выпишите для Гарри и его друзей все составы смесей. Порядок элемента в смеси значения не имеет. Смесь может состоять и из одного вещества.
Формат входных данных:
В первой строке входного файла записано целое число: N – количество имеющихся элементов. В следующих N строках записаны названия элементов. (0<N<=100)
Формат выходных данных:
Выходной файл должен содержать перечень всех возможных вариантов смешивания по одному варианту в строке. Вариант смешивания задается перечнем номеров исходных элементов, записанных через пробел. Варианты могут быть выведены в произвольном порядке.
Пример:
| INPUT.TXT | OUTPUT.TXT |
| сера пепел растертый зуб вампира | 1 2 1 3 2 3 1 2 3 |
Задача 7. «N элементов смеси» 10 баллов. Бывает, что Северус Снегг вносит в условия приготовления смесей некоторые ограничения. В прошлый вторник, например, ему захотелось иметь рецепты смесей, в которых ровно 13 составляющих веществ. А вчера он потребовал приготовить смеси из 7 элементов. Напишите для Гарри программу получения нужных смесей.
Формат входных данных:
В первой строке входного файла записано 2 числа: N – количество имеющихся веществ и М – необходимое количество веществ в смеси. В следующих N строках записаны названия элементов. (0<N, М<=100)
Формат выходных данных:
Выходной файл должен содержать перечень всех возможных вариантов смешивания по одному варианту в строке. Вариант смешивания задается перечнем номеров исходных элементов, записанных через пробел. Варианты могут быть выведены в произвольном порядке.
Пример:
| INPUT.TXT | OUTPUT.TXT |
| 3 2 сера пепел растертый зуб вампира | 1 2 1 3 2 3 |
Задача 8. «Шахматы» 10 баллов Хотя Гарри Поттер и учится в совершенно волшебной школе Хогварц, но каникулы-то он проводит в мире маглов, поэтому магловские игры Гарри знает достаточно хорошо. Умеет он играть и в шахматы. И раз уж Северус Снегг заставил нас вспомнить классические задачи комбинаторики, то не лишним будет решить еще одну «наиклассическую» задачу о ладьях. Требуется расположить на шахматной доске ладей так, чтобы они не угрожали друг другу.
Будем считать, что доска имеет размеры N x N клеток и на ней стоят N ладей.
Задача 9. Еще одна «классика» мира маглов. Расставить на шахматной доске размером N x N клеток N ферзей так, чтобы они не били друг друга.
Задача 10. 10 баллов А ещеГарри научил Рона игре в «морской бой», и теперь они на всех уроках тихонечко (только с дымом от орудий, но без «Ба-а-ах!») ведут морские сражения. Сделайте доброе дело, напечатайте заготовку для игры в «морской бой» для Рона. Считается, что эскадра состоит из 15 кораблей (1 – 5-клеточный, 2 – 4-клеточных, 3 – 3-клеточных, 4 – 2-клеточных, 5 – 1-клеточных). Все корабли «линейные», на поле они не должны касаться друг друга. Поле боя имеет размер 10х10 клеток.