codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![](https://espresso.codeforces.com/b44312777a76084e866261383f069b57dda713fc.png) divisible by 10 we take it.
     10 4. In case we have no numbers of second and third type, we take a number ![](https://espresso.codeforces.com/b44312777a76084e866261383f069b57dda713fc.png) 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 ![](https://espresso.codeforces.com/cb0172a656698061aefa8eb30b2dbcd1e31f508e.png) 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)