15,936,850 members
1.00/5 (1 vote)
See more:
The task is to write a program, which for every given natural number n will generate not so long text made of not so big number of signs, which has exactly n different subsequences. But remember that subsequence with 0-length is also the subsequence. We consider subsequences to be different if their text is different. For instance sequence "ioi" has seven subsequences (i,o,ii,io,oii,ioi and empty subsequence).

I have no idea, how to start biting this.
Does anyone have an idea how to solve it?

What I have tried:

I've already tried to determine some kind of relation between the number of subsequences and a number of appearances of each letter, I also tried to do a brute force solution, but finally, everything, which seemed to work didn't have any sense.
Posted
Updated 11-Aug-22 6:55am

Solution 1

You have to create subsequences which you may create, need to compare, so you need a class SubSequence or Sequence which has an "equal" function. This "equal" function may be something like:
C++
```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```

Tip: even if not all works some parts will do, and you get hopefully enough points ;-)

Solution 2

This is a problem from an ongoing competition (https://sio2.mimuw.edu.pl/c/oi26-1/p/pod/). Please do not answer this question until November 13.