Максимальное количество кусочков, на которое можно разбить слово

@55molnia55 · Регистрация: 23.11.2019

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

Помогите решить задачу.
Дано: в первой строке вводится число n(от 1 до 10), потом в n строках вводится слова(длина не более $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{6}$ ).
Вывести: Для каждого слова на отдельной строке нужно вывести одно число — максимальное количество кусочков, на которое его можно разбить (симметричные кусочки должны совпадать).
Пример: deleted => (d)(e)(let)(e)(d) => 5
racecar => (r)(a)(c)(e)(c)(a)(r) => 7

@Dax · 24.11.2019, 17:59

Примерно, понял, как разбить

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
import textwrap
 
 
def choper(mstr, n):
    res = textwrap.wrap(mstr, n)
    print(res)
    return res
 
 
if __name__ == '__main__':
    mstr = input()
    n = int(input())
    choper(mstr, n)

@55molnia55 · 24.11.2019, 18:21 **[ТС]**

Это не решает задачу. Возможно вы не правильно поняли условие. Сейчас приведу задачу полностью:
Недавно Глеб начал играть в «Magicka». К сожалению, это для него новая игра, и сейчас он
учится колдовать.
Заклинание — это слово из строчных латинских букв. Учить заклинания целиком довольно тяжело, поэтому Глеб разбивает их на кусочки, учит эти кусочки, а затем объединяет вместе. Cклеить
заклинание из кусочков можно только в том случае, если симметричные кусочки совпадают, то есть
первый кусочек совпадает с последним, второй — с предпоследним, и так далее. Например, у decode
ровно два разбиения: (de)(co)(de) и (decode). Понятно, что у любого заклинания есть разбиение
на один кусочек.
Так как Глеб сейчас занимается подготовкой задачи, помогите ему найти разбиение для заклинания s, состоящее из максимального количества кусочков.
Первая строка содержит количество тестов t (от 1 до 10).
Следующие t строк содержат по одному заклинанию s.

Для каждого теста на отдельной строке выведите одно число — максимальное количество кусочков, на которое его можно разбить.

Пример:
4
bonobo
deleted
racecar
racecars

выведет:
3
5
7
1

@Viktorrus · 25.11.2019, 05:33

55molnia55, У Вас в условии противоречие.

Сообщение от 55molnia55

Например, у decode
ровно два разбиения: (de)(co)(de) и (decode).

написано, что два разбиения.
А у слова ниже с аналогичным разбиением

Сообщение от 55molnia55

bonobo

написано, что 3 разбиения.
Хотя здесь разбиение аналогично предыдущему
(bo)(no)(bo) и (bonobo).

Рыжий Лис · 25.11.2019, 06:08

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

У Вас в условии противоречие.

Никакого противоречия. Ищется же максимальное разбиение кусочков.

Добавлено через 14 минут

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import re
 
t = 'racecar'
 
count = 0
while True:
    t2 = re.sub(r'(\w+)(\w*)\1', r'\2', t)
    print(t2)
    if t == t2:
        break
    count += 2
    t = t2
if t2:
    count += 1
print(count)

@eaa · 25.11.2019, 07:23

Рыжий Лис, Ваша программа решает только некоторые частные случаи.

Смущает 10⁶,еще и 10 тестов, по генерации и подсчету задача не сложная за квадрат.

@Viktorrus · 25.11.2019, 07:51

Рыжий Лис, Но эти два слова с одинаковым количеством кусочков. Или какой еще вариант с кусочками во втором слове, которого я не вижу? Может быть Вы правы, просто я не вижу еще одного разбиения во втором слове.

@eaa · 25.11.2019, 08:11

Viktorrus, тут нужно найти длину, а не количество вариантов. По этому ответ 3.

Рыжий Лис · 25.11.2019, 08:11

eaa, не знаю, возможно, не правильно понял задание и нужно откусывать по одному символу (а сейчас написана жадная регулярка). Да и нет проверки на невалидные данные (хотя должно просто выдать 1 - не проверял).

Viktorrus, какое слово? 'deleted'? По идее любое слово можно разбить как '(deleted)'. Будет 1.

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@55molnia55 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 8

	Максимальное количество кусочков, на которое можно разбить слово 24.11.2019, 17:07. Показов 2071. Ответов 8 Метки python 3.x (Все метки) Помогите решить задачу. Дано: в первой строке вводится число n(от 1 до 10), потом в n строках вводится слова(длина не более $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{6}$ ). Вывести: Для каждого слова на отдельной строке нужно вывести одно число — максимальное количество кусочков, на которое его можно разбить (симметричные кусочки должны совпадать). Пример: deleted => (d)(e)(let)(e)(d) => 5 racecar => (r)(a)(c)(e)(c)(a)(r) => 7 0

@55molnia55 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 8
	24.11.2019, 18:21 [ТС]
	Это не решает задачу. Возможно вы не правильно поняли условие. Сейчас приведу задачу полностью: Недавно Глеб начал играть в «Magicka». К сожалению, это для него новая игра, и сейчас он учится колдовать. Заклинание — это слово из строчных латинских букв. Учить заклинания целиком довольно тяжело, поэтому Глеб разбивает их на кусочки, учит эти кусочки, а затем объединяет вместе. Cклеить заклинание из кусочков можно только в том случае, если симметричные кусочки совпадают, то есть первый кусочек совпадает с последним, второй — с предпоследним, и так далее. Например, у decode ровно два разбиения: (de)(co)(de) и (decode). Понятно, что у любого заклинания есть разбиение на один кусочек. Так как Глеб сейчас занимается подготовкой задачи, помогите ему найти разбиение для заклинания s, состоящее из максимального количества кусочков. Первая строка содержит количество тестов t (от 1 до 10). Следующие t строк содержат по одному заклинанию s. Для каждого теста на отдельной строке выведите одно число — максимальное количество кусочков, на которое его можно разбить. Пример: 4 bonobo deleted racecar racecars выведет: 3 5 7 1 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.11.2019, 07:23
	Рыжий Лис, Ваша программа решает только некоторые частные случаи. Смущает 10⁶,еще и 10 тестов, по генерации и подсчету задача не сложная за квадрат. 0

@Viktorrus 1732 / 970 / 199 Регистрация: 22.02.2018 Сообщений: 2,693 Записей в блоге: 6
	25.11.2019, 07:51
	Рыжий Лис, Но эти два слова с одинаковым количеством кусочков. Или какой еще вариант с кусочками во втором слове, которого я не вижу? Может быть Вы правы, просто я не вижу еще одного разбиения во втором слове. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.11.2019, 08:11
	Viktorrus, тут нужно найти длину, а не количество вариантов. По этому ответ 3. 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	25.11.2019, 08:11
	eaa, не знаю, возможно, не правильно понял задание и нужно откусывать по одному символу (а сейчас написана жадная регулярка). Да и нет проверки на невалидные данные (хотя должно просто выдать 1 - не проверял). Viktorrus, какое слово? 'deleted'? По идее любое слово можно разбить как '(deleted)'. Будет 1. 0