Задача палиндромы

@Artem0303 · Регистрация: 25.05.2020

Студворк — интернет-сервис помощи студентам

Дана строка s. Вы можете менять местами символы любое количество раз. Например, если
s = "aebecda", вы можете, например, поменять местами символы так, чтобы получился строку "abacede".
После того, как вы перемешайте символы, вам нужно разделить строку на несколько подстрок(по крайней мере на одну). Каждый символ исходной строки должен принадлежать ровно одной подстроке. К примеру,
последний строку можно разделить так: "aba | c | ede".
Нужно разделить строки так, чтобы каждая подстрока был палиндромом.
Напомним, что палиндром - строка, одинаково читается в обоих направлениях (слева направо и
справа налево).
Разделите строку так, чтобы длина минимального палиндрома была максимальна. Найдите эту
длину.

Формат входных данных
Первая строка содержит строку s (1 + 6 | s | 6105), который состоит только из букв английского
алфавита в нижнем регистре.

Формат выходных данных
Выведите одно целое число - ответ на эту задачу.

Примеры
standard input / standard output
aebecda / 1
eutxutuatgextu / 7

@eaa · 09.10.2020, 13:55

подсчет. четность/нечетность. на вскидку.

@Gdez · 09.10.2020, 14:42

Artem0303,

Python
1
2
3
st = input()
k = sum(1 for i in set(list(st)) if st.count(i) % 2)
print((len(st) - k) // k + 1)

@eaa · 09.10.2020, 14:50

Сообщение от Gdez

1 for i in set(list(st)) if st.count(i) % 2

прекрати квадратить эту задачу! минус в "репу"

@Gdez · 09.10.2020, 15:04

eaa, можно разбить, но пусть пробуют "читать" и сами разбивают, если свои наработки не выкладывают...
Я сам в начале пишу, потом "собираю" так

@Olkam · 13.10.2020, 23:27

st = input()
k = sum(1 for i in set(list(st)) if st.count(i) % 2)
print((len(st) - k) // k + 1)

Тут не совсем верно. В стартовом топике для "aebecda", можно разбить на "aba" "с" "ede"
Тогда минимальное значение 1, а по данному алгоритму будет 2

@Gdez · 13.10.2020, 23:39

Olkam, добавь условие вместо print

Python
1
2
3
4
if (len(st) - k) // 2 - k < 0:
    print(1)
else :
    print(#в коде)

@Olkam · 13.10.2020, 23:57

А если k=0? например при строке "aabbcc"

@Gdez · 14.10.2020, 00:01

Olkam,

добавляй условия
ТС не нужно было...
Может еще, что увидишь

@Olkam · 14.10.2020, 00:04

Да я просто вредничаю -) Не пойму, зачем вообще подобная задача

@Gdez · 14.10.2020, 00:06

Python
1
2
3
4
5
6
 if not k:
    print(len(st))
elif (len(st) - k) // 2 - k < 0:
    print(1)
else :
    print(#в коде)

Добавлено через 1 минуту
Olkam, на таких "простых" задачках много сыпятся - не все граничные условия сразу видны

@Olkam · 14.10.2020, 00:58

Хотя такой задачей можно помучать студентов.

Добавлено через 5 минут
Спасибо за консультацию

Добавлено через 9 минут
Хотя если дать строку "ааааа", то надо еще условие добавлять

Добавлено через 36 минут
или "aeaeaeae"
алгоритм выдает "8", а по идее должно быть "1"

@Gdez · 14.10.2020, 04:29

Olkam, "aaaaa" => 5 ; "aeaeaeae" => 8 => "ааееееаа"
Строка разбивается так, чтобы минимальный палиндром был максимально возможным. Иначе для любой строки ответом будет => 1.

@pancho · 15.10.2020, 19:29

Товарищи, объясните пожалуйста, что писать в конце ибо при проверке всегда выходит один

@Gdez · 15.10.2020, 20:52

pancho, вроде это

Python
1
2
3
4
5
6
7
8
st = input()
k = sum(1 for i in set(list(st)) if st.count(i) % 2)
if not k:
    print(len(st))
elif (len(st) - k) // 2 - k < 0:
    print(1)
else :
    print((len(st) - k) // k + 1)

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

Задача палиндромы

Решение

Решение

@Artem0303 0 / 0 / 0 Регистрация: 25.05.2020 Сообщений: 17

	Задача палиндромы 09.10.2020, 13:35. Показов 18509. Ответов 14 Метки нет (Все метки) Дана строка s. Вы можете менять местами символы любое количество раз. Например, если s = "aebecda", вы можете, например, поменять местами символы так, чтобы получился строку "abacede". После того, как вы перемешайте символы, вам нужно разделить строку на несколько подстрок(по крайней мере на одну). Каждый символ исходной строки должен принадлежать ровно одной подстроке. К примеру, последний строку можно разделить так: "aba \| c \| ede". Нужно разделить строки так, чтобы каждая подстрока был палиндромом. Напомним, что палиндром - строка, одинаково читается в обоих направлениях (слева направо и справа налево). Разделите строку так, чтобы длина минимального палиндрома была максимальна. Найдите эту длину. Формат входных данных Первая строка содержит строку s (1 + 6 \| s \| 6105), который состоит только из букв английского алфавита в нижнем регистре. Формат выходных данных Выведите одно целое число - ответ на эту задачу. Примеры standard input / standard output aebecda / 1 eutxutuatgextu / 7 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.10.2020, 13:55
	подсчет. четность/нечетность. на вскидку. 0

@Gdez 8838 / 4490 / 1864 Регистрация: 27.03.2020 Сообщений: 7,312
	09.10.2020, 15:04
	eaa, можно разбить, но пусть пробуют "читать" и сами разбивают, если свои наработки не выкладывают... Я сам в начале пишу, потом "собираю" так 0

@Olkam 2 / 1 / 1 Регистрация: 11.10.2020 Сообщений: 8
	13.10.2020, 23:57
	А если k=0? например при строке "aabbcc" 0

@Gdez 8838 / 4490 / 1864 Регистрация: 27.03.2020 Сообщений: 7,312
	14.10.2020, 00:01
	Olkam, добавляй условия ТС не нужно было... Может еще, что увидишь 1

@Olkam 2 / 1 / 1 Регистрация: 11.10.2020 Сообщений: 8
	14.10.2020, 00:04
	Да я просто вредничаю -) Не пойму, зачем вообще подобная задача 1

@Olkam 2 / 1 / 1 Регистрация: 11.10.2020 Сообщений: 8
	14.10.2020, 00:58
	Хотя такой задачей можно помучать студентов. Добавлено через 5 минут Спасибо за консультацию Добавлено через 9 минут Хотя если дать строку "ааааа", то надо еще условие добавлять Добавлено через 36 минут или "aeaeaeae" алгоритм выдает "8", а по идее должно быть "1" 0

@Gdez 8838 / 4490 / 1864 Регистрация: 27.03.2020 Сообщений: 7,312
	14.10.2020, 04:29
	Olkam, "aaaaa" => 5 ; "aeaeaeae" => 8 => "ааееееаа" Строка разбивается так, чтобы минимальный палиндром был максимально возможным. Иначе для любой строки ответом будет => 1. 1

@pancho 0 / 0 / 0 Регистрация: 15.10.2020 Сообщений: 15
	15.10.2020, 19:29
	Товарищи, объясните пожалуйста, что писать в конце ибо при проверке всегда выходит один 0