All you have to do is implement following algorithm:
- If we have numbers 0 or 100, we take them to needed subset.
- If we got number greater than 0 and less than 10, we take it.
- If we got number divisible by 10 we take it.
- In case we have no numbers of second and third type, we take a number that is not divisible by 10
There are at most two ways to represent rational fraction as continued. Using Euclid algorithm you can do that for and then check equality of corresponding ai.
First of all, let's carry over all powers of two in the following way: if we have ai = aj, i ≠ j, carry 1 to ai + 1. Now as all of ai are distinct, the answer is max(ai) — cnt(ai) + 1, where max(ai) — maximal value of ai,cnt(ai) — size of a
First of all let's consider a graph on a number line. It's neccesary to have edges i - > i + 1(first type). Also you can edges like i - > i + k + 1 (second type). Other edges are forbidden. This allows us to understand whether the answer is 0 or not. Also answer is 0 when all edges of second type doesn't intersect, considering them to be segments of number line, except when k ≥ n - 1 — in this case answer is 1. Now we know that answer != 0. Frow all edges we have let's use only second type edges. If there aren't any of this edges we can add 1 to the answer, because of possibility of adding 0 edges to graph. For every vertex i, that has possibility of adding second type edges, let's add to answer 2cnt, cnt — amount of vertexes on [i, min(i + k, n — k — 1)] without edges of second type out of them. Also it is necessary for all the second type edges to start in this segment.
Let's consider substring of s s[i... j], that all characters from i to j are palindrome centers, and i - 1, j + 1 are not. Every such substring can be treated independently from the others, and as we don't need to know it'sstructure let's consider only it length len. Let's calculate grundy[len] — Grundy function. If we want to cut character at position i 0 ≤ i < len then our game splits in to independent ones: first will have length i - 1, second — len - i - 2, as s[i - 1] and s[i + 1] are not centers of palindrome any more.