60.md (2720B)
1 Source: https://codeforces.com/blog/entry/1317 2 3 **Problem A.** Solution - *O*(*n*2). 4 5 We take phrase and parse it. Mark all cells, that obviously didn't match - *O*(*n*). In the end we go through the array and count all unmarked cells. 6 7 If 0 - we print "-1", else - amount of unmarked cells. 8 9 **Problem B.** Solution - *O*(*k* × *n* × *m*). 10 11 We start BFS from given point. Go from cell to all 6 directions. The answer - number of visited cells. 12 13 **Problem C**. Solution - *O*(27 × *n*2). 14 15 We can see, that in connected component - if we know 1 number - then we know all others in component, because in each pare we know minimal and maximal 16 17 power of each primes. Because number of different primes in one number " < = 1000000" is less, than 7, we can look over all possibilities of 1 number in connected compoment - and for each number, that we get, we check, that it suits. 18 19 How to check? We can notice, that if we know *a*, (*a*, *b*), [*a*, *b*], then , start DFS and check. 20 21 **Problem D.** Solution - *O*(max numebr). 22 23 We can notice, that each beautiful triplet has form - (*x*2 - *y*2, 2*xy*, *x*2 + *y*2). Now we can gen all such triples. For each triple, we watch - if we have more than 1 number in given set - we union them. 24 25 How to gen all the triples? 26 27 *x* > *y*. 28 29 . This means, that . 30 31 Now for gen all this triples we an take -  и . The number of iterations - . 32 33 what means - "union"? 34 35 We take a data structure named DSU. If two number belong to one beautiful triple - they are connected with edge, in our situation - we can union corresponding to them unions. 36 37 **Problem E**. Solution - *O*(*n* + *log*(*xy*)). 38 39 We can see, that after one minute the sum changes - it multiply on 3, and substract first and last elements of sequence. Because of that we can count of sum with help of power of matrix. 40 41 What happens after sorting. 42 43 First number stay on his place. On the last place - *F**x**a**n* + *F**x* - 1*a**n* - 1. Where *n* - number of elements, ans *F**x* - *x* Fibonacci number - with *F*- 1 = 0 and *F*0 = 1. 44 45 This means - that we can count the last number with matrix too. 46 47 After that we use the first idea. 48 49 If you have questions - ask them.