Рядковий автомат
Рядковий автомат «Гомер-2015» приймає на вхід рядок символів і повертає деякий рядок як результат. В автомата є певний набір інструкцій — список правил заміни. Кожнеправило складається з підрядка, який потрібно замінити, і рядка, на який цей підрядок потрібно замінити. Автомат послідовно робить такі операції: шукає першу в списку заміну таку, що поточний рядок містить відповідний підрядок, міняє перше входження цього підрядка на відповідний рядок-заміну і повторює все спочатку. Коли жоден підрядок у поточному рядку не міститься, автомат повертає цей рядок як результат. Список замін автомата називається програмою. Кількість правил замін називається розміром програми. Кількість зроблених замін на конкретних вхідних даних називається кількістю операцій.
Розглянемо приклад, коли на вхід автомат приймає рядок abcbca, а його програма розміру 2 має такий вигляд: 1)bac → c і 2) bc → cba. Порядок дій автомата такий:
Поточним рядком є abcbca.
Оскільки abcbca не містить підрядк аbac з першого правила, автомат переходить до другого правила.
Оскільки abcbca містить підрядок bc з другого правила, автомат заміняє перше входження цього підрядка наcba і повертається на початок.
Поточним рядком є acbabca.
Оскільки acbabca не містить підрядк аbac з першого правила, автомат переходить до другого правила.
Оскільки acbabca містить підрядок bc з другого правила, автомат заміняє перше (і єдине) входження цього підрядка на cba і повертається на початок.
Поточним рядком є acbacbaa.
Оскільки acbacbaa містить підрядок bac з першого правила, автомат заміняє перше (і єдине) входження цього підрядка на c і повертається на початок.
Поточним рядком є accbaa.
Оскільки accbaa не містить підрядк аbac з першого правила, автомат переходить до другого правила.
Оскільки accbaa не містить підрядк аbc з другого правила, автомат намагається перейти до наступного правила.
Оскільки правила закінчилися, автомат повертає рядок accbaa як результат.
Таким чином, з рядка abcbca автомат утворив accbaa. Кількість операцій у даному випадку дорівнює 3: замінилиbc на cba, потім ще раз bc на cba, далі bac на c.
Завдання
Напишіть набір програм для рядкового автомата, що вирішують різноманітні задачі перетворення рядків (див. нижче). Для кожної підзадачі ви здаєте лише текст програми рядкового автомата.За кожну підзадачу ви отримуєте або повний бал за відповідну підзадачу, якщо програма пройшла всі її тести, або нуль, якщо хоча б один тест даної підзадачі не пройдено.
Обмеження
У кожному правилі довжина як підрядка пошуку, так і рядка заміни не повинна перевищувати 10 символів (але в сумі вони можуть бути довшими); при цьому рядок заміни може бути порожнім, а підрядок пошуку — ні. Автомат завжди може оперувати такими символами: цифри, малі та великі латинські літери (причому малі та великі літери в розумінні автомата — різні символи), а також символ «плюс» (+). Ви можете користуватися всіма цими символами як у підрядках пошуку, так і в рядках заміни в усіх підзадачах. Розмір однієї програми не може перевищувати 100. Для жодних вхіднихданих кількість операцій не повинна перевищувати 1000. Означення розміру програми та кількості операцій див. вище.
Перевірка за допомогою емулятора
В електронному варіанті умов наведено посилання для завантаження програми, що емулює рядковий автомат та надає допоміжну інформацію про перебіг виконання програми. Щоб використати емулятор, розташуйте його в окремому каталозі, створіть у цьому каталозі файл program.txt з текстом програми, а також файл input.txt, у який введіть вхідний рядок для вашої програми (можна додати або не додавати перенесення рядка в кінці файла), та запустіть програму-емулятор. Вона створить такі файли:
!output.txt: вихідний рядок автомата (якщо програма чи вхідні дані некоректні або кількість операцій перевищує обмеження, файл не буде створено / буде видалено).
!debug.txt:у кожному рядку цього файла вказано стан рядка після відповідної кількості операцій (якщо програма чи вхідні дані некоректні, цей файл не буде створено / буде видалено; якщо кількість операцій перевищує обмеження, файл міститиме стан рядка тільки до моменту, коли було перевищено обмеження).
!info.txt: у першому рядку цього файла вказано, чи є коректними програма та вхідні дані (а якщо вони некоректні, то чому); якщо програма та вхідні дані коректні, у другому рядку вказано кількість операцій виконаної програми; у третьому рядку вказано розмір програми; у четвертому рядку вказано довжину найдовшого рядка пошуку та довжину найдовшого рядка заміни.
Додатково емулятору можна передавати до чотирьох параметрів командного рядка: обмеження на кількість операцій, на розмір програми, на довжину рядка пошуку та на довжину рядка заміни. Наприклад, якщо запустити емулятор командою auto.exe 2000 100 15, обмеженням на кількість операцій буде встановлено 2000 (замість 1000); обмеження на розмір програми буде стандартним (100); обмеження на довжину рядка пошуку — 15; невказане в параметрах командного рядка обмеження на довжину рядка заміни також залишиться стандартним (10).
Підзадача 1 (5 балів)
На вході — рядок з цифр довжини від 1 до 20 включно. На виході — рядок із тих самих цифр у порядку від найменших до найбільших. Приклад: 9101→0119.