АВТ
Language: Russian
English

Remote Training on Programming

Problems Online status Contests
News FAQ E-learning
For authors:
Register  ||  Login
 
Hello, Guest! Please login or register.

775. Сжатие текста

Time Limit: 2 seconds
Memory Limit:65536KB
Points:100
View Problem Statistics Submit Problem added debug

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

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

Входные данные
В первой строке входного файла задано целое число R - количество 
заменяемых последовательностей и целое число N - количество строк 
в исходном тексте (1<=N<=1000). Далее следуют R пар строк, 
описывающих возможные замены. Первая строка каждой пары 
содержит заменяемую последовательность, а вторая - заменяющий символ, 
являющийся большой или маленькой английской буквой. Различным заменяемым 
последовательностям соответствуют разные английские буквы (большие и 
маленькие буквы различаются). В следующих N строках записан текст, 
подлежащий сжатию. В этом тексте, также как и в заменяемых 
последовательностях, отсутствуют буквы английского алфавита.

Выходные данные
В выходной файл вывести заархивированный текст.

Примечания
Символы перевода строки не заменяются (т.е. замены возможны 
только внутри строк). Длина каждой строки входного файла не превосходит 
255 символов.

Пример входного файла
8 10
рхиватор
b
замен
D
ены
F
зам
G
быт
h
про
d
сжат
f
ом называется
g
Архиватором называется программа, предназначенная для сжатия данных за счет удаления 
избыточной информации. В этой задаче вашей целью является разработка простейшего 
архиватора текстов на русском языке. В таких текстах многие знаки стандартной таблицы 
символов не встречаются, поэтому они могут быть использованы для замены часто 
повторяющихся последовательностей символов. 

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

Пример выходного файла
Аbg dграмма, предназначенная для fия данных за счет удаления 
изhочной информации. В этой задаче вашей целью является разработка dстейшего 
аbа текстов на русском языке. В таких текстах многие знаки стандартной таблицы 
символов не встречаются, поэтому они могут hь использованы для Dы часто 
повторяющихся последовательностей символов. 

Заданы последовательности, которые могут hь DF некоторыми символами английского 
алфавита, а также исходный текст, который следует fь. Поскольку в исходном тексте эти 
последовательности могут накладываться друг на друга, результат fия существенно зависит 
от порядка D. Ваша задача состоит в том, чтобы получить fый текст наименьшей длины.

View Problem Statistics Submit Problem discussion Author/source: olympiads.ru
Educational Courses / Problems from olympiads.ru /
68. 240 - Equation with Missing Digits 775. 69. 242 - Spaces in Cube 776. 249 - Шифровка 2 778. 252 - Дейкстра
time generating 0.109 sec.
© Copyright VSU, AVT, Nosov D.A., Andrianov I.A.