584.md (5758B)
1 Source: https://codeforces.com/blog/entry/20766 2 3 [584A - Olesya and Rodion](/contest/584/problem/A "Codeforces Round 324 (Div. 2)") 4 5 Two cases: *t* = 10 and *t* ≠ 10. 6 7 If *t* = 10 then there are two cases again :). If *n* = 1 then answer is - 1 (because there is not any digit divisible by *t*). If *n* > 1, then answer, for example, is '1111...110' (contains *n* - 1 ones). 8 9 If *t* < 10 then answer, for example, is 'tttttttt' (it, obviously, divisible by *t*). 10 11 [584B - Kolya and Tanya](/contest/584/problem/B "Codeforces Round 324 (Div. 2)") 12 13 The number of ways to choose *a**i* (without any conditions) — 33*n*. Let *A* be the number of ways to choose *a**i* with condition that in every triangle gnomes have 6 coins. Then answer is 33*n* - *A*. 14 15 Note that we can separate all gnomes on n independent triangles (*i*-th triangle contains of *a**i*, *a**i* + *n*, *a**i* + 2*n*, *i* < *n*). So we can count answer for one triangle and then multiply the results. To count answer for one triangle, we can note that there are 7 ways to choose gnomes with 6 coins (all permutations 1, 2, 3 and 2, 2, 2). 16 17 So answer is — 33*n* - 7*n*. We count it in *O*(*n*). 18 19 [584C - Marina and Vasya](/contest/584/problem/C "Codeforces Round 324 (Div. 2)") 20 21 Let's find a string that will be equal to *s*1 in *k* = *n* - *t* positions and equal to *s*2 in *k* = *n* - *t* positions. Let's denote *q* = quantity of *i* that *s*1*i* = *s*2*i*. If *k* ≤ *q*, then let's take *k* positions such that *s*1*pos* = *s*2*pos* and put in answer the same symbols. Then put in other *n* - *k* positions symbols, which are not equal to corresponding in *s*1 and *s*2 (we can do it, because we have 26 letters). 22 23 Now *k* > *q*. So, if there is an answer, where exists *pos* such that *s*1*pos* = *s*2*pos*, *s*1*pos* ≠ *ans**pos*, let's denote *ans**i* = *s*1*i*, and then in any position such that *s*1*i* ≠ *s*2*i* = *ans**i* and *s*1*i* = *ans**i* (and in the same position in *s*2) we will choose *a**i*, such that *a**i* ≠ *s*1*i* and *a**i* ≠ *s*2*i* (we can do it because *k* > *q*). So, for every position from *q* we can put symbols, equal to corresponding symbols in *s*1 and *s*2. Now we have strings *s*1, *s*2 of length *n* - *q* (such that *s*1*i* ≠ *s*2*i* for every i) and we should find string *ans* such that *f*(*ans*, *s*1) = *f*(*ans*, *s*2). We know that *s*1*i* ≠ *s*2*i*, so *ans**i* may be equal to corresponding in *s*1 or to corresponding in *s*2 or not equal to *s*1*i* and to *s*2*i*. So, we need, at least, 2(*k* - *q*) symbols in answer to make *f*(*s*1, *ans*) = *k* - *q* and *f*(*s*2, *ans*) = *k* - *q*. Consequently, if *n* - *q* < 2(*k* - *q*), the answer is - 1, and else just put first *k* - *q* symbols in answer from *s*1, next *k* - *q* symbols from *s*2, and others won't be equal to corresponding in *s*1 and *s*2. 24 25 Solution works in *O*(*n*). 26 27 [584D - Dima and Lisa](/contest/584/problem/D "Codeforces Round 324 (Div. 2)") 28 29 There is a fact that the distance between adjacent prime numbers isn't big. For *n* = 109 maximal distanse is 282. So let's find maximal prime *p*, such that *p* < *n* - 1 (we can just decrease n while it's not prime(we can check it in )). We know that *n* - *p* < 300. Now we have even (because *n* and *p* are odd) number *n* - *p* and we should divide it into a sum of two primes. As *n* - *p* < 300, we can just iterate over small primes *P* and check if *P* is prime and *n* - *p* - *P* is prime. You can check that there is a solution for all even numbers less than 300 by bruteforce. 30 31 [584E - Anton and Ira](/contest/584/problem/E "Codeforces Round 324 (Div. 2)") 32 33 We can consider that we pay 2|*i* - *j*| coins for swap (we can divide answer in the end). Then we can consider that we pay |*i* - *j*| coins for moving *p**i* and |*i* - *j*| for moving *p**j*. So, if *x* was on position *i* and then came to position *j*, then we will pay at least |*i* - *j*| coins. Then the answer is at least  (*pp* — position *k* in permutation *p*, and *ps* — position *k* in permutation *s*). Let's prove that this is the answer by showing the algorithm of making swaps. 34 35 Let's consider that permutation *s* is sorted (our task is equal to it). Then we will put numbers from *n* to 1 on their positions. 36 37 How we can put *n* on its position? Denote *p**pos* = *n*. Let's prove that there exists a position *pos*2 such that *pos* < *pos*2 and *p**pos*2 ≤ *pos*(then we will swap *p**pos*2 with *n* (and both numbers will move to their final positions and *n* will move to the right, so we can repeat this process until *n* returns to its position)). We can note that there are only *n* - *pos* positions that are bigger than *pos*. And how many numbers on these positions can be bigger than *pos*? We can say that answer is *n* - *pos*, but it's incorrect, because *n* is bigger than *pos*, but *pos**n* ≤ *pos*. Now we can use Pigeonhole principle and say that position *x*, such that *x* > *pos* and *p**x* ≤ *pos* exists. 38 39 But now our algorithm is *O*(*n*3). How we can put *n* in its position in *O*(*n*) operations? Let's move the pointer to the right while number is bigger than *pos*. Then swap *n* with found number. After we can move pointer from new *n*'s position, so pointer always moves to the right and will not do more then *n* steps.