Формат входного файла:
N
слово1
...
словоN
где N - число слов от 2 до 12 (всегда четное). Длина каждого слова не превышает 20 символов.
Формат выходного файла:
слово слово процент_совпадения
...
слово слово процент_совпадения
где:
в каждой паре слова стоят в алфавитном порядке.
пары отсортированы в алфавитном порядке по первым словам в них.
Пример входного файла:
8
Оля
Ира
Катя
Наташа
Сережа
Илья
Коля
Саша
Файл результата для данного примера:
Илья Оля 67
Ира Сережа 67
Катя Коля 50
Наташа Саша 75
Решение g6_1092:
Вначале нам потребуется отсортировать слова - в дальнейшем это избавит нас от любых дополнительных действий по сортировке. Так как слов всего 12, то достаточно использовать сортировку пузырьком.
Теперь следует построить таблицу совпадений. Напишем процедуру, которая принимает два слова и выдает процент совпадения так, как это определено в условии. Для этого нам потребуется находить максимальную общую подпоследовательность. Эта подзадача решается методом динамического программирования. Пустим два вложенных цикла - один по буквам первого слова, второй - по буквам второго. В ячейке A[i, j] таблицы будет храниться длина наибольшей подпоследовательности из i первых букв первого слова и j первых букв второго слова. В таком случае, если на текущем шаге буквы совпали, то A[i, j] := A[i-1, j-1], а в случае не совпали A[i, j] = max(A[i-1, j], A[i, j-1]). Теперь просто возьмем правый нижний элемент таблицы - он и будет длиной наибольшей общей подпоследовательности, а, зная ее процент совпадения, определяем как длину подпоследовательности умноженную на 100 и деленную на длину меньшего слова, а затем округленную до ближайшего целого.
Таблица совпадений для всех пар успешно построена. Теперь надо организовать эффективный перебор всех возможных пар для выбора лучшего решения. Также нам надо стремиться к тому, чтобы решение было выведено сразу в нужном формате. Т.к. наш массив слов уже отсортирован, то это означает, что первое слово в паре должно стоять перед вторым словом, а также первые слова пар должны быть упорядочены.
Напишем рекурсивную процедуру, которая будет подставлять первое слово текущей пары на первое свободное место, а затем пытаться подставить второе слово пары на любую последующую позицию. Как только все пары будут созданы, следует проверить, лучше ли текущее решение, чем текущий максимум. Для вывода достаточно помнить, в какой паре находится какое слово (одномерный массив из 12 элементов, в каждом из которых хранится число от 1 до 6). Сложность работы рекурсии будет O(N!!), т.е. для N=12: 11*9*7*5*3=10395, что вполне приемлемо.
Ну и вывод совсем простой: цикл по парам, и вывод всех встретившихся слов, а затем вывод процента совпадений (для этого надо запомнить номера слов и вывести соответствующий элемент из таблицы совпадений).
Задача g6_1093: Несвязные области (Самарская областная олимпиада по информатике 2001).
На плоскости произвольным образом размещают N (1
Входные данные:
В первой строке входного файла input.txt содержится число N. В каждой из следующих N строк располагаются координаты одного прямоугольника: координаты левого верхнего (ai,bi) и правого нижнего (ci, di) углов.
Ограничения:
-10000
-10000
Выходной файл output.txt: число (несвязных областей).
Пример входного файла:
2
0 1 1 0
0 2 1 0
output.txt для данного примера:
3
Решение g6_1093:
Решение этой задачи опирается на те же методы, которые использованы в задаче #1041 - Квадраты.
Мы также заносим все координаты x и y в два массива, сортируем их по возрастанию, удаляем равные элементы из массивов и пересчитываем координаты прямоугольников уже в новой системе (где новая координата прямоугольника - индекс элемента массива, содержащего старую координату).
Теперь все координаты наших прямоугольников лежат в пределах от 1 до 100. Это позволяет завести нам двумерный массив и дальнейшее решение осуществлять на нем.
Каждая ячейка новой сетки должна содержать пять флагов: входит ли эта клетка в какой-либо прямоугольник и четыре флага, указывающие, проходит ли по какой-либо границе (левой, правой, верхней или нижней) этой клетки граница какого-либо прямоугольника.
Устанавливать первый флаг очень просто: для этого достаточно перебрать все прямоугольники и пометить все клетки, которые в них входят. С границами все несколько хитрее - во-первых, надо пройтись циклом по всем x, входящим в прямоугольник и пометить, что нижние клетки прямоугольника имеют нижнюю границу, а верхние - верхнюю. Точно также надо пустить цикл по y, с пометкой левых и правых границ.
Однако если просто сделать так, то дальнейшее решение будет несколько осложнено. Поэтому, на этапе разметки, следует устанавливать еще некоторые границы. Допустим, мы установили наличие левой границы у какой-то клетки. В этом случае, нам надо также установить правую границу у клетки, которая лежит слева от нее. Точно также для всех других направлений. Т.е. все границы становятся "двусторонними"
Следующим этапом будет выделение несвязных областей. Это можно сделать несколькими способами: рекурсивным, обходом в ширину, сканированием. Следует внимательно следить, чтобы процедура не переходила на непомеченные клетки (в которых нет ни одного прямоугольника) и не перескакивала через границы клеток.
К полученному результату следует прибавить единицу - внешнюю область.
Задача g6_1094: Космический мусорщик (Всероссийская командная олимпиада школьников по информатике 2002).
Решение g6_1094:
В околоземном космическом пространстве накопилось много мусора, поэтому ученые сконструировали специальный аппарат - ловушку для космического мусора. Для того чтобы хорошо собирать мусор, этот аппарат должен двигаться по достаточно сложной траектории, сжигая собранный по пути мусор. Ловушка может передвигаться в пространстве по 6 направлениям: на север (N), на юг (S), на запад (W), на восток (E), вверх (U) и вниз (D). Движением ловушки управляет процессор. Программа движения задается шестью правилами движения, которые соответствуют каждому из указанных направлений. Каждое такое правило представляет собой строку символов из множества {N, S, W, E, U, D}.
Команда ловушки есть пара из символа направления и параметра - целого положительного числа M. При исполнении такой команды ловушка в соответствии со своей программой выполняет следующее. Если параметр больше 1, то она перемещается на один метр в направлении, которое указано в команде, а затем последовательно выполняет команды, заданные правилом для данного направления, с параметром меньше на 1. Если же параметр равен 1, то просто перемещается на один метр в указанном направлении.
Пусть, например, заданы следующие правила:
Направление
|
Правило
|
N
|
N
|
S
|
NUSDDUSE
|
W
|
UEWWD
|
E
|
-
|
U
|
U
|
D
|
WED
|
|