Задачи с ZContest
https://www.spoj.pl/ZEL08/problems/ZMAR/
Нормальный алгоритм Маркова — вещь довольно известная в теории алгоритмов. Почитать можно много где, не рассказывать же, как делается поиск в Интернете... Изложим несколько упрощенную схему. Имеем некоторый набор символов (алфавит), и строку из этих символов. Кроме того, имеем правила замены, в каждом из которых указано, какую подстроку с исходной строке нужно заменить, и на что ее менять. Подстроки могут быть и пустыми. Порядок правил фиксирован. Функционирует все следующим образом. Правила просматриваются в указанном порядке на предмет применимости. Первое же правило, которое может быть применено, однократно применяется (то есть выполняется описанная в нем замена), после чего цикл обработки повторяется (список просматривается заново). "Однократно" означает, что если в строке к моменту выполнения правила существует несколько подстрок, которые могут быть заменены, то заменяется только одна подстрока из возможных, а именно — самая левая. Процесс заканчивается, если после очередного просмотра строка не изменилась. В процессе выполнения замен длина строки может изменяться, увеличиваться, уменьшаться – всё пожалуйста.
Начальная непустая строка была получена из обычного арифметического выражения путем удаления всех символов, кроме открывающейся и закрывающейся круглой скобки. Требуется написать последовательность команд, которая приводит эту строку к строке "
RIGHT" либо "
WRONG" в зависимости от того, верно или неверно были расставлены скобки в исходной строке в соответствии с обычными правилами записи арифметических выражений. Например, строку
()((())()) предлагаемая последовательность замен должна перевести в
RIGHT, а строку
(() та же самая последовательность замен должна перевести в строку
WRONG.
Начальная строка представляет из себя произвольную строку типа [число1]
+[число2]
=? где [число1] и [число2] — десятичные записи некоторых натуральных чисел. Требуется написать последовательность замен, которая переведет эту запись в завись вида [число1]
+[число2]
=[сумма], где [сумма] — десятичная запись результата сложения числа 1 и числа 2. Ну, то есть строка
2+2=? должна быть переведена в
2+2=4, а строка
25+76=? та же самая последовательность замен должна перевести в
25+76=101. Длина исходной строки любая (то есть в качестве слагаемых могут быть представлены большие натуральные числа (в данной задаче до 100 знаков)).
Задана строка из больших букв английского алфавита (символы от A до Z), заканчивающаяся знаком вопроса "?". Необходимо вывести их в обратном порядке, уже без знака вопроса. То есть строка
ABBCD? должна стать строкой
DCBBA
Задано двоичное число, состоящее из 0 и 1. Необходимо вывести его в виде набора букв z. Где количество таких букв равно заданному двоичному числу. То есть для
110 алгоритм должен вывести
zzzzzz
Задана строка из больших букв английского алфавита (символы от A до Z)), заканчивающаяся знаком вопроса "?". Надо написать набор правил, который отсортирует её по возрастанию и выведет без знака вопроса. В отсортированном виде
DFAAS? будет выглядеть как
AADFS.
Задано два десятичных числа через символ подчеркивания "_" и затем строка "=?", например
30_42=?. Требуется вывести вместо них значение наибольшего общего делителя для этой пары. Для
30_42=? это будет
6.
Замечание: Ограничение на увеличение строки составляет 100000 символов.
Ещё замечание: правила записываются в виде БЫЛО->СТАЛО, так что "-", ">" и пробелы из алфавита исключаем. Это чтобы единообразие было в ответах.
... << RSDN@Home 1.2.0 alpha rev. 655>>