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

@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.

Новые блоги и статьи Все статьи Все блоги /
Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .
Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .

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

	Максимальное количество кусочков, на которое можно разбить слово 24.11.2019, 17:07. Показов 2140. Ответов 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

Опции темы