305.md (3388B)
1 Source: https://codeforces.com/blog/entry/7712 2 3 ## [305A - Strange Addition](/contest/305/problem/A "Codeforces Round 184 (Div. 2)") 4 5 All you have to do is implement following algorithm: 6 7 1. If we have numbers 0 or 100, we take them to needed subset. 8 2. If we got number greater than 0 and less than 10, we take it. 9 3. If we got number  divisible by 10 we take it. 10 4. In case we have no numbers of second and third type, we take a number  that is not divisible by 10 11 12 [Solution](http://pastebin.com/nQXi0Khh) 13 14 ## [305B - Continued Fractions](/contest/305/problem/B "Codeforces Round 184 (Div. 2)") 15 16 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*. 17 18 [Solution](http://pastebin.com/x4rXtxen) 19 20 ## [305C - Ivan and Powers of Two](/contest/305/problem/C "Codeforces Round 184 (Div. 2)") 21 22 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* 23 24 [Solution](http://pastebin.com/RrRe5ffR) 25 26 ## [305D - Olya and Graph](/contest/305/problem/D "Codeforces Round 184 (Div. 2)") 27 28 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. 29 30 [Solution O(n + m)](http://pastebin.com/JaL2y2Gc) [Solution O(m + log(n))](http://pastebin.com/GRKqSsmH) 31 32 ## [305E - Playing with String](/contest/305/problem/E "Codeforces Round 184 (Div. 2)") 33 34 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. 35 36 [Solution](http://pastebin.com/niiD2WDM)