Обработка математики: 100%
images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
06/04/2025 18:05:30

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

831. Лишние буквы

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Дана символьная строка S длины N (0 ≤ N ≤ 100) и словарь, который содержит M слов (0 ≤ M ≤ 100), длина каждого из которых не превышает N. Строка и слова состоят из символов a, b, …, z.
Напишите программу, которая определяет наименьшее количество символов, которое необходимо вычеркнуть из заданной строки S, чтобы результирующую строку можно было представить как последовательность слов словаря. Количество использований каждого слова не ограничивается. Считается, что пустую строку можно представить с помощью слов любого словаря.
В первой строке входного файла находится два целых числа N и M, разделенных пробелом. Во второй строке находится символьная строка S. В каждой из следующих M строк находится слово словаря.
В единственной строке выходного файла должно находиться натуральное число – минимальное количество вычеркиваний, после которых зашифрованная строка может быть представлена в виде последовательности слов словаря.

Пример ввода

11 5
abafchtdsya
aba
a
bach
dsy
zero

Пример вывода

2
Примечание: Строка в примере после вычеркивания лишних букв f и t примет вид abachdsya (было сделано два вычеркивания: abafchtdsya), и может быть представлена как последовательность следующих слов: a, bach, dsy, a.
XIV Всеукраинская олимпиада по информатике, 2001
loading