Задача про количество вхождений строк

@Victoria_Memo · Регистрация: 11.03.2024

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

Ограничение времени - 1 секунда
Ограничение памяти - 256Mb

Дано натуральное число $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ . Рассмотрим множество $https://www.cyberforum.ru/cgi-bin/latex.cgi?S$ , которое содержит все строки длины $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ , состоящие из строчных букв латинского алфавита. $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(s)$ -- количество вхождений строки «qwertyu» в $https://www.cyberforum.ru/cgi-bin/latex.cgi?s$ .

От вас требуется вычислить $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{s \in S}f(s)$ -- сумму $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(s)$ по всем строкам $https://www.cyberforum.ru/cgi-bin/latex.cgi?s \in S$

Формат ввода

На вход подается единственное число $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ ( $https://www.cyberforum.ru/cgi-bin/latex.cgi?1 \le n \le 19$ ).

Формат вывода

В единственную строку выведите ответ на задачу.

Примеры:

Ввод
Code
1
7
Вывод
Code
1
1

@Catstail · 06.04.2024, 15:02

Python
1
2
3
4
5
6
7
8
n=int(input())
if n<7:
    print(0)
else:
    s=0
    for k in range(n-6):
        s=s+26**k+26**(n-7-k)
    print(s)

@Red white socks · 07.04.2024, 07:25

Catstail, что-то совсем не в ту степь. Начиная с 7.
Самое интересное начинается, конечно, с n=14.

Добавлено через 3 минуты
Хотя нет, интересно не получается, условие максимально лояльно к решающим.

@Catstail · 07.04.2024, 07:37

Red white socks, комбинаторика... Не настаиваю.

YuS_2 · 07.04.2024, 13:16

Сообщение от Red white socks

не получается

у меня именно так...
n - натуральное число, длина строки
S - множество строк с длиной n, количество строк не указано...
s - есть подозрение, что это каждая строка длины n
f(s) - количество вхождений строки "qwertyu" в отельной строке s, каждая из которых принадлежит множеству S
строки состоят из строчных латинских букв (26 штук), из каких именно символов состоит каждая строка - не указано.

Требуется вычислить сумму всех f(s), сколько их, тоже не указано...

Допустим:
n = 7 и все строки s одинаковые (не знаю сколько их, не указано в условии), s = "abcdefg"

Внимание вопрос:
А сколько тут вхождений строки "qwertyu"?

Сопутствующие вопросы, зависящие от округленности моих глаз:
Почему в примере, ответ - 1?
Скорее всего, я туплю и чего-то недопонял в условии... но чего именно?

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

комбинаторика...

Хмм... как и почему?

@Catstail · 07.04.2024, 14:00

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

Хмм... как и почему?

Я рассуждал так:

1) если n < 7, то ответ = 0 (т.к. длина строки больше длины любой строки из S_n при n < 7
2) если n=7, то из всего множества S₇ вхождение только одно
3) если n>7, то все вхождения заданной строки можно представить как:

___qwertyu---

где длины строк "___" и "---" в сумме составляют n-7

YuS_2 · 07.04.2024, 15:47

Catstail, да
1) Тут без вопросов, всё логично
2) А вот тут... S₇ - это что? Множество длиной 7 или один элемент из множества, длиной 7? По идее, 7 - длина строки должна быть n, т.е. один из элементов множества, который имеет длину 7. Допустим что так, но почему вхождение появилось? Ведь символы (7 штук) абсолютно неизвестны... вхождения может и не быть... а длина множества S какова, сколько в ней строк, что суммировать-то?

3) Допустимо. Но нам необходимы для ответа именно вхождения, их количество, вся длина строки не имеет значения в задаче... не понимаю - как они определяются, есть или нет?

Стою на асфальте я в лыжи обутый - то ли лыжи не едут, то ли я ... ну, дальше все знают. Вот сижу и не втыкаю от слова совсем.

@Catstail · 07.04.2024, 20:48

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

S₇ - это что?

- у меня это множество всех строк длины 7, состоящее из всех букв лат. алфавита.

YuS_2 · 07.04.2024, 22:13

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

это множество всех строк длины 7, состоящее из всех букв лат. алфавита.

Да. Складывается впечатление, что это задача-конструктор, в которой каждый составляет условия самостоятельно, по своему усмотрению...

Правда неясно одно в этом случае, зачем в ней пример?
По логике:
1. если цель задачи посчитать сумму вхождений, то символы алфавита могут повторяться в строках.
2. как формируются строки? Какова вероятность, что в строках вообще есть вхождение строки-шаблона "qwertyu"? Вопросы никуда не делись...
3. если нет ограничения в количестве строк, то допустимо бесконечное их число и как следствие, никаких цифр мы получить не сможем, только алгоритм с несколькими неизвестными...
4. По п.3. выбивается из логики то, что есть пример в задаче, в котором указано единственное число в качестве входных данных и получаемый результат, тоже в виде единственного числа.
тупик.

В Вашем решении, при вводе 7, получается результат 2, что не соответствует примеру...

В общем,

@Catstail · 07.04.2024, 23:14

YuS_2, Да, моё решение неверное (есть ошибка + неполнота, т.к. 19 > 14)

@Red white socks · 08.04.2024, 01:16

YuS_2, не мутите воду. Задача задана четко и однозначно.

@idealist · 08.04.2024, 01:24

Ну, ответ будет 0 при q > n,
а в остальных случаях
res = (n-q+1)*a^(n-q),
где a - длина алфавита,
q - длина заданной строки,
т.е. для нашего случая:
res = (n-7+1)*26^(n-7) = (n-6)*26^(n-7)

@Catstail · 08.04.2024, 07:32

idealist, Согласен. Но когда n >= 14 можно разместить уже две строки...

@idealist · 08.04.2024, 08:37

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

Но когда n >= 14 можно разместить уже две строки...

А, да, этот момент я не учел)))

YuS_2 · 08.04.2024, 09:47

Сообщение от Red white socks

не мутите воду. Задача задана четко и однозначно.

Вы предполагаете, что я тут троллингом, что ли занимаюсь? Так я отвечу: нет.
Вопросы, ответы на которые я не увидел пока, выше заданы в сообщениях 5,7,9. Если есть желание пояснить - ответьте, пожалуйста.
Четко и ясно - это только в том случае, в котором с первого раза (только глянул на задачу и сразу понятны все нюансы), условия становятся понятны даже неподготовленному человеку. Здесь, в данной задаче, ничего четкого и ясного не наблюдается от слова совсем. Я, конечно, не великий программист и математик, но немного разбираюсь в теме, а все заданные вопросы выше, не для красного словца прозвучали.

@Red white socks · 08.04.2024, 10:14

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

Вы предполагаете, что я тут троллингом, что ли занимаюсь?

Именно так.

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

Здесь, в данной задаче, ничего четкого и ясного не наблюдается от слова совсем

На мой взгляд, тут обратная ситуация. Ваши сообщение вызывают ... недоумение.

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

S - множество строк с длиной n, количество строк не указано...

Посчитайте сами. Все в задаче для этого есть

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

s - есть подозрение, что это каждая строка длины n

нет. Это элемент множества S.

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

f(s) - количество вхождений строки "qwertyu" в отельной строке s, каждая из которых принадлежит множеству S
строки состоят из строчных латинских букв (26 штук), из каких именно символов состоит каждая строка - не указано.

В первой части отвечаете на вторую часть вопроса.

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

Допустим:
n = 7 и все строки s одинаковые (не знаю сколько их, не указано в условии), s = "abcdefg"
Внимание вопрос:
А сколько тут вхождений строки "qwertyu"?

А вы перестали пить коньяк по утрам?

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

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

условия становятся понятны даже неподготовленному человеку

Ерунда.
Условия должны быть понятны человеку, на которого рассчитана задача.

Добавлено через 5 минут
Задано множество S - множество всех слов заданной длины. На этом множестве задана числовая функция. Требуется найти сумму значений функции по всем элементам множества.

YuS_2 · 08.04.2024, 20:35

Сообщение от Red white socks

Именно так.

Вы вправе думать что угодно, но я уже сказал, что это не так.

Сообщение от Red white socks

На мой взгляд, тут обратная ситуация. Ваши сообщение вызывают ... недоумение.

В каком месте? Процитируйте.

Сообщение от Red white socks

Посчитайте сами. Все в задаче для этого есть

Что мне непонятно, я обозначил в своих вопросах.

Сообщение от Red white socks

нет. Это элемент множества S.

В таком случае, чего нет-то? Что является элементами множества S? Разве не строки? Вы о чем вообще?
А раз единичный элемент множества S - это s, то значит подозрение:

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

s - есть подозрение, что это каждая строка длины n

- соответствует действительности.

Сообщение от Red white socks

В первой части отвечаете на вторую часть вопроса.

Какого именно вопроса? Там где возникли у меня вопросы, там стоят вопросительные знаки.

Сообщение от Red white socks

А вы перестали пить коньяк по утрам?

Я тоже могу вести разговор в подобном стиле... но обычно такие диалоги ничем хорошим не заканчиваются. Только, я не понял, что вызвало вашу агрессию?

Сообщение от Red white socks

Ерунда.

Вы вместо четких ответов на поставленные вопросы решили заняться троллингом с многозначительными намеками? На что именно пытаетесь намекнуть? Да и зачем, в принципе? Я вам чем-то насолил или обидел?
Нет желания отвечать - не отвечайте. Есть желание ответить - ответьте. Только щеки надувать не надо, это неконструктивно абсолютно.

Сообщение от Red white socks

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

Конечно. Только вот условия должны быть составлены понятным образом, а не подразумевать, что отвечающий знает на какую тему задана задача и подразумевать какие-то данные не оговоренные в условиях. Это глупость, если это так... глупость составителя задачи, а не отвечающего.

Сообщение от Red white socks

Задано множество S - множество всех слов заданной длины.

Ну хоть какой-то конструктив.
В качестве уточнения могу привести цитаты:

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

множество , которое содержит все строки длины , состоящие из строчных букв латинского алфавита.

Картинки в цитате отсутствуют, но надеюсь понятно:
- здесь нет ничего о словах, речь идет о строках длины n, из которых состоит множество S. Не множество длины n, а строки длины n. Или чего, правила русского языка позволяют Вам прочитать условия как-то по-другому?

Сообщение от Red white socks

На этом множестве задана числовая функция. Требуется найти сумму значений функции по всем элементам множества.

В этой части вообще никаких вопросов не возникало. Все вопросы написаны выше.

@Red white socks · 09.04.2024, 09:34

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

здесь нет ничего о словах, речь идет о строках длины n, из которых состоит множество S.

В комбинаторике словом называют произвольную последовательность из заданного алфавита.
Еще раз.
Требуется подсчитать сумму значений функций по всем элементам множества.
У вас вызывает проблема с определением множества?
Не заходите тогда в комбинаторику. Проходите мимо.

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

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

Рассмотрим множество , которое содержит все строки длины , состоящие из строчных букв латинского алфавита.

Здесь указано все достаточно ясно.
Все (все, понимаете, ВСЕ) строки длины n из заданного алфавита.

YuS_2 · 09.04.2024, 10:29

Сообщение от Red white socks

В комбинаторике словом называют произвольную последовательность из заданного алфавита.

Мы в разделе комбинаторики разве?

Сообщение от Red white socks

У вас вызывает проблема с определением множества?

Именно. В данной задаче в условиях нет ничего о границах множества.

Сообщение от Red white socks

Не заходите тогда в комбинаторику. Проходите мимо.

На это могу только сказать: протрите глаза, поднимите их вверх и прочитайте название раздела, в котором мы находимся... А куда мне заходить, я решу сам, без ваших указаний.

Сообщение от Red white socks

Все (все, понимаете, ВСЕ) строки длины n из заданного алфавита.

Не раздувайте щеки, я уже говорил... просто ткните пальцем в условие, которое указывало бы на количество строк длиной n (количество элементов множества, если так понятнее будет), принадлежащих множеству. Или укажите в чем я ошибаюсь или чего не понял... А скандирование слова "все" - это не объяснение и тем более никакой не аргумент.
Заодно, можно также ткнуть пальцем в то, на основании чего определяется вхождение указанного в условии шаблона строки "qwertyu" в каждый из элементов множества (s). Это тоже непонятно (для меня)

PS Я же просил... если нет желания объяснять - не пишите ничего (это не жизненная необходимость для меня и я ничего ни от кого не требую, и никто никому ничем не обязан

), если оно таки есть, объясните на пальцах, я не троллингом тут занялся, повторяю в очередной раз. А раздувание щек и утверждения без расшифровки - это не объяснение, кроме удивления это ничего не вызывает...

@Red white socks · 09.04.2024, 10:49

YuS_2, вы просто засрали тему. Вот и всё.

Добавлено через 5 минут
Если вы не можете посчитать количество всех строк заданной длины, то это исключительно Ваши проблемы, не надо раскатывать простыни.

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	07.04.2024, 07:25
	Catstail, что-то совсем не в ту степь. Начиная с 7. Самое интересное начинается, конечно, с n=14. Добавлено через 3 минуты Хотя нет, интересно не получается, условие максимально лояльно к решающим. 0

@Catstail Супер-модератор 38167 / 21102 / 4307 Регистрация: 12.02.2012 Сообщений: 34,690 Записей в блоге: 14
	07.04.2024, 07:37
	Red white socks, комбинаторика... Не настаиваю. 0

YuS_2 Любознательный 7404 / 2254 / 360 Регистрация: 10.03.2016 Сообщений: 5,213
	07.04.2024, 15:47
	Catstail, да 1) Тут без вопросов, всё логично 2) А вот тут... S₇ - это что? Множество длиной 7 или один элемент из множества, длиной 7? По идее, 7 - длина строки должна быть n, т.е. один из элементов множества, который имеет длину 7. Допустим что так, но почему вхождение появилось? Ведь символы (7 штук) абсолютно неизвестны... вхождения может и не быть... а длина множества S какова, сколько в ней строк, что суммировать-то? 3) Допустимо. Но нам необходимы для ответа именно вхождения, их количество, вся длина строки не имеет значения в задаче... не понимаю - как они определяются, есть или нет? Стою на асфальте я в лыжи обутый - то ли лыжи не едут, то ли я ... ну, дальше все знают. Вот сижу и не втыкаю от слова совсем. 0

@Catstail Супер-модератор 38167 / 21102 / 4307 Регистрация: 12.02.2012 Сообщений: 34,690 Записей в блоге: 14
	07.04.2024, 23:14
	YuS_2, Да, моё решение неверное (есть ошибка + неполнота, т.к. 19 > 14) 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	08.04.2024, 01:16
	YuS_2, не мутите воду. Задача задана четко и однозначно. 0

@idealist 3750 / 1944 / 612 Регистрация: 21.11.2021 Сообщений: 3,707
	08.04.2024, 01:24
	Ну, ответ будет 0 при q > n, а в остальных случаях res = (n-q+1)a^(n-q), где a - длина алфавита, q - длина заданной строки, т.е. для нашего случая: res = (n-7+1)26^(n-7) = (n-6)*26^(n-7) 1

@Catstail Супер-модератор 38167 / 21102 / 4307 Регистрация: 12.02.2012 Сообщений: 34,690 Записей в блоге: 14
	08.04.2024, 07:32
	idealist, Согласен. Но когда n >= 14 можно разместить уже две строки... 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	09.04.2024, 10:49
	YuS_2, вы просто засрали тему. Вот и всё. Добавлено через 5 минут Если вы не можете посчитать количество всех строк заданной длины, то это исключительно Ваши проблемы, не надо раскатывать простыни. 0