Обои – III (Рисунок) (150 баллов)
Задачу добавил: alef
Успешно сдано решений: 1
И каких только обоев не было в магазинах торговой сети «ГиперСтрой»! Самые разные рисунки, оттенки… А особенно впечатляющими были обои из последнего поступления, которые – если правильно наклеивать полосы на стену – образуют крупные красивые узоры. Словом, устоять перед такой красотой оказалось невозможным, но теперь необходимо заново подсчитать количество рулонов. Узор состоит из фрагментов одинаковой высоты, которые будем обозначать прописными латинскими буквами; разным фрагментам соответствуют разные буквы. При наклейке полос узор всегда должен начинаться сверху, все полосы должны быть цельными. Ваша задача – написать программу, позволяющую оценить, сколько нужно приобрести рулонов.
Формат входного файла input.txt
Первая строка – целые числа U и L через пробел
U – количество различных фрагментов узора (все фрагменты имеют одинаковую высоту) (1<=U<=26)
L – длина одного рулона обоев в фрагментах узора (1<=L<=50)
Вторая строка – L символов – описание рулона обоев. Символы – прописные латинские буквы; задействуются буквы с № 1 до № U (например, если U=3, то используются символы A, B, C)
Третья строка содержит два целых числа T и S через пробел
T – высота участка, который нужно оклеить, в фрагментах (1<=T<=L)
S – ширина участка, который нужно оклеить, в полосах обоев (1<=S<=15)
Следующие S строк – «горизонтальное» описание узора, который должны образовать обои. Каждая из этих строк содержит T символов.
Формат выходного файла output.txt
Первая строка – целое число – количество рулонов, которое нужно, чтобы оклеить заданный участок стены
Гарантируется, что решение всегда существует
Пример входного файла
6 11
ABCDEBCDEBF
5 4
ABCDE
BCDEB
CDEBF
CDEBF
Пример выходного файла
2