Let's fix the number a of strings of length p and the number b of strings of length q. If a·p + b·q = n, we can build the answer by splitting the string s to a parts of length p and b parts of length q, in order from left to right. If we can't find any good pair a, b then the answer doesn't exist. Of course this problem can be solved in linear time, but the constraints are small, so you don't need linear solution.
Complexity: O(n2).
612B - HDD is Outdated Technology
You are given the permutation f. Let's build another permutation p in the following way: pfi = i. So the permutation p defines the number of sector by the number of fragment. The permutation p is called inverse permutation to f and denoted f - 1. Now the answer to problem is .
Complexity: O(n).
612C - Replace To Make Regular Bracket Sequence
612D - The Union of k-Segments