Question

Сегодня Петя узнал про то, что слова, которые одинаково читаются слева направо и справа налево, называются палиндромами. С помощью кубиков с буквами из английского набора своего брата Петя выложил фразу WEWISHYOUAMERRYCHRISTMAS (кубики стоят рядом, без пробелов), а теперь хочет переставить кубики местами, и возможно часть кубиков убрать, так, чтобы оставшееся слово (не обязательно осмысленное) оказалось палиндромом. Какое наименьшее количество кубиков Пете придется убрать?

Answer 1

Ответ:

5 букв

Пошаговое объяснение:

Если я правильно поняла, то может может получится набор букв, грубо говоря. В таком случае нам нужны буквы, которые повторяются 2 (или просто чётное количество раз) и одна, у которой не будет пары. Считаем буквы W-2, E-2, I-2, S-3, H-2, Y-2, O-1, U-1, A-2, M-2, R-3, C-1, T-1. Получается лишние буквы (при использовании 3 букв S) -O, U, R(1), C, T - это и есть наименьшее число букв - 5

Answer 2

Чтобы определить наименьшее количество кубиков, которые Пете придется убрать, чтобы оставшееся слово стало палиндромом, нужно найти наибольшую подпоследовательность (LCS) исходного слова, которая будет являться палиндромом.

В данном случае, исходное слово - WEWISHYOUAMERRYCHRISTMAS. Чтобы найти наибольшую палиндромную подпоследовательность, можно использовать алгоритм динамического программирования, известный как "Наибольшая Общая Подпоследовательность" (LCS).

Сначала создадим матрицу размером (n x n), где n - длина исходного слова. Заполним матрицу следующим образом:

1. Если символы на позициях i и j равны, то элемент матрицы в позиции (i, j) равен элементу матрицы в позиции (i-1, j-1) плюс 1.
2. Если символы на позициях i и j не равны, то элемент матрицы в позиции (i, j) равен максимуму из элементов матрицы в позициях (i-1, j) и (i, j-1).

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

В данном случае, наибольшая палиндромная подпоследовательность равна 13 (WESUYUUYSIW). Чтобы сделать слово палиндромом, Пете нужно оставить только эту подпоследовательность и убрать остальные кубики. Следовательно, Пете придется убрать 19 - 13 = 6 кубиков.

Таким образом, наименьшее количество кубиков, которые Пете придется убрать, равно 6.