Оптимизация системы команд
Задачу добавил: alef
Успешно сдано решений: 0
Конечно, в компании нашелся инженер, который заметил, что подход к разработке
системы команд процессора, когда специальные команды вводятся, чтобы заменить
наиболее длинные последовательности элементарных команд, неоптимален.
И он предложил другой подход:
неэлементарные команды можно заменять последовательностью не только
элементарных команд,
но и других неэлементарных (которые, конечно, придется ввести в систему команд).
Главное, чтобы длина последовательности (количество команд в ней) не превышала
заданную. Задача состоит в том, чтобы найти наименьшее количество
неэлементарных команд, которые нужно
ввести в систему команд процессора.
Формат входного файла input.txt
Первая строка - целые числа N (1<=N<=50) - максимальная длина
последовательности элементарных команд,
K (1<=K<=100) - количество элементарных команд, M (1<=M<=100) -
исходное количество неэлементарных команд
следующие K строк содержат элементарные команды процессора
(по одной в строке, каждая может состоять из латинских букв и цифр)
Следующие за ними M строк содержат информацию в формате:
<неэлементарная команда>
<пробел> <список элементарных команд>, где <список элементарных команд> - это
элементарные команды, записанные через пробел
Каждая команда (как элементарная, так и неэлементарная) может состоять
из латинских букв
и цифр, длина команды - не более 20 символов
Формат выходного файла output.txt
Целое число - количество неэлементарных команд, которые были добавлены
в систему команд процессора
Пример входного файла
3 3 7
if
then
goto
copy goto if if then goto if goto then
shift goto if
trunc if goto then
jump goto goto if goto then
loop if then goto if goto then
sleep if then goto
flap if goto if then goto
Пример выходного файла
3