Member 14041718 Ответов: 2

Генерирующая строка с n неповторяющимися подпоследовательностями

Задача состоит в том, чтобы написать программу, которая для каждого заданного натурального числа n будет генерировать не такой длинный текст из не такого большого числа знаков, который имеет ровно n различных подпоследовательностей. Но помните, что подпоследовательность с 0-длиной также является подпоследовательностью. Мы считаем подпоследовательности разными, если их текст отличается. Например, последовательность "Мио" состоит из семи фрагментов (я,о,ИИ,Ио,ТОО,Мио и пустую последовательность).

Я понятия не имею, как начать кусать это.
У кого-нибудь есть идея, как ее решить?

Спасибо заранее

Что я уже пробовал:

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

2 Ответов

Рейтинг:
1

Member 14042680

Это проблема из-за продолжающейся конкуренции (https://sio2.mimuw.edu.pl/c/oi26-1/p/pod/). Пожалуйста, не отвечайте на этот вопрос до 13 ноября.

Рейтинг:
0

KarstenK

Вы должны создавать подпоследовательности, которые вы можете создавать, должны сравнивать, поэтому вам нужен класс подпоследовательности или последовательности, который имеет "равную" функцию. Эта "равная" функция может быть чем-то вроде:

bool operator==(const SubSequence &op)
bool isSubsequence(SubSequence *seq);//some test if seq is in object
//other functions
SubSequence(string text);//create instance
SubSequence* allSubsequences();//function which returns an array of all subsequence

Совет: даже если не все работает, некоторые части будут делать, и вы получите, надеюсь, достаточно очков ;-)