305A - Strange Addition

All you have to do is implement following algorithm:

1. If we have numbers 0 or 100, we take them to needed subset.
2. If we got number greater than 0 and less than 10, we take it.
3. If we got number divisible by 10 we take it.
4. In case we have no numbers of second and third type, we take a number that is not divisible by 10

Solution

305B - Continued Fractions

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 a_i.

Solution

305C - Ivan and Powers of Two

First of all, let's carry over all powers of two in the following way: if we have a_i = a_j, i ≠ j, carry 1 to a_i + 1. Now as all of a_i are distinct, the answer is max(a_i) — cnt(a_i) + 1, where max(a_i) — maximal value of a_i,cnt(a_i) — size of a

Solution

305D - Olya and Graph

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 2^cnt, 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.

Solution O(n + m) Solution O(m + log(n))

305E - Playing with String

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.

Solution