НачалоПодразделы
Другие разделы
| 829. Делители |
| 830. Лабиринт |
| 832. Доставка |
Дата и время
17/11/2024 01:16:40
831. Лишние буквы
Лишние буквы
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 17/03/2008 | Школьные сборы, день 1 (C) |
| 17/03/2008 | Школьные сборы, дорешивание (1C) |
| 14/10/2014 | Занятие 7 (C) |
| 21/03/2024 | ДП + Игры 1 (проводит BOGAT) (G) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
XIV Всеукраинская олимпиада по информатике, 2001
