450.md (6535B)
1 Source: https://codeforces.com/blog/entry/13112 2 3 #### [450A - Jzzhu и дети](/contest/450/problem/A "Codeforces Round 257 (Div. 2)") 4 5 You can simply simulate it or find the last maximum *ceil*(*a**i* / *m*). 6 7 #### [450B - Jzzhu и последовательности](/contest/450/problem/B "Codeforces Round 257 (Div. 2)") 8 9 We can easily find that every 6 numbers are the same. It's like {*x*, *y*, *y* - *x*, - *x*, - *y*, *x* - *y*, *x*, *y*, *y* - *x*, ...}. 10 11 #### [449A - Jzzhu и шоколад](/contest/449/problem/A "Codeforces Round 257 (Div. 1)") / [450C - Jzzhu и шоколад](/contest/450/problem/C "Codeforces Round 257 (Div. 2)") 12 13 We assume that *n* ≤ *m* (if *n* > *m*, we can simply swap *n* and *m*). 14 15 If we finally cut the chocolate into *x* rows and *y* columns (1 ≤ *x* ≤ *n*, 1 ≤ *y* ≤ *m*, *x* + *y* = *k* + 2), we should maximize the narrowest row and maximize the narrowest column, so the answer will be *floor*(*n* / *x*) * *floor*(*m* / *y*). 16 17 There are two algorithms to find the optimal (*x*, *y*). 18 19 1. Notice that if *x* * *y* is smaller, the answer usually will be better. Then we can find that if *k* < *n*, the optimal (*x*, *y*) can only be {*x* = 1, *y* = *k* + 1} or {*x* = *k* + 1, *y* = 1}. If *n* ≤ *k* < *m*, the optimal (*x*, *y*) can only be {*x* = 1, *y* = *k* + 1}. If *m* ≤ *k* ≤ *n* + *m* - 2, the optimal (*x*, *y*) can only be {*x* = *k* + 2 - *m*, *y* = *m*}, because let *t* = *m* - *n*, *n* / (*k* + 2 - *m*) ≥ (*n* + *t*) / (*k* + 2 - *m* + *t*) ≥ 1. 20 2. *floor*(*n* / *x*) has at most  values, so we can enum it and choose the maximum *x* for each value. 21 22 #### [449B - Jzzhu и города](/contest/449/problem/B "Codeforces Round 257 (Div. 1)") / [450D - Jzzhu и города](/contest/450/problem/D "Codeforces Round 257 (Div. 2)") 23 24 We consider a train route (1, *v*) as an undirected deletable edge (1, *v*). 25 26 Let *dist*(*u*) be the shortest path between 1 and *u*. We add all of the edges (*u*, *v*) weighted *w* where *dist*(*u*) + *w* = *dist*(*v*) into a new directed graph. 27 28 A deletable edge (1, *v*) can be deleted only if it isn't in the new graph or the in-degree of *v* in the new graph is more than 1, because the connectivity of the new graph won't be changed after deleting these edges. Notice that you should subtract one from the in-degree of *v* after you delete an edge (1, *v*). 29 30 #### [449C - Jzzhu и яблоки](/contest/449/problem/C "Codeforces Round 257 (Div. 1)") / [450E - Jzzhu и яблоки](/contest/450/problem/E "Codeforces Round 257 (Div. 2)") 31 32 Firstly, we should notice that 1 and the primes larger than *N* / 2 can not be matched anyway, so we ignore these numbers. 33 34 Let's consider each prime *P* where 2 < *P* ≤ *N* / 2. For each prime *P*, we find all of the numbers which are unmatched and have a divisor *P*. Let *M* be the count of those numbers we found. If *M* is even, then we can match those numbers perfectly. Otherwise, we throw the number 2*P* and the remaining numbers can be matched perfectly. 35 36 Finally, only even numbers may be unmatched and we can match them in any way. 37 38 #### [449D - Jzzhu и числа](/contest/449/problem/D "Codeforces Round 257 (Div. 1)") 39 40 Firstly, we can use inclusion-exclusion principle in this problem. Let *f*(*x*) be the count of number *i* where *A**i*&x = *x*. Let *g*(*x*) be the number of 1 in the binary respresentation of *x*. Then the answer equals to . 41 42 Now the task is to calculate *f*(*x*) for every integer *x* between 0 and 220. Let *f**k*(*x*) be the count of number *i* where *Y*0&X0 = *X*0 and *X*1 = *Y*1 (they are defined below). 43 44 We divide *x* and *A**i* into two parts, the first *k* binary bits and the other 20 - *k* binary bits. Let *X*0 be the first part of *x* and *X*1 be the second part of *x*. Let *Y*0 be the first part of *A**i* and *Y*1 be the second part of *A**i*. 45 46 We can calculate *f**k*(*x*) in *O*(1): 47 48  49 50 The problem can be solved in *O*(*n* * 2*n*) now (*n* = 20 in this problem). 51 52 #### [449E - Jzzhu и квадраты](/contest/449/problem/E "Codeforces Round 257 (Div. 1)") 53 54 Consider there is only one query. 55 56  57 58 Let me descripe the picture above. 59 60 A grid-square can be exactly contained by a bigger square which coincide with grid lines. Let *L* be the length of a side of the bigger square. Let *i* be the minimum distance between a vertice of the grid-square and a vertice of the bigger square. Let *f*(*L*, *i*) be the number of cells which are fully contained by the grid-square. 61 62 We can divide a grid-square into four right triangles and a center square. For each right triangle, the number of cells which are crossed by an edge of the triangle is *L* - *gcd*(*i*, *L*). Then, the number of cells which are fully contained by the triangle is [*i*(*L* - *i*) - *L* + *gcd*(*i*, *L*)] / 2. 63 64 *f*(*L*, *i*) = (*L* - 2*i*)2 + 2[*i*(*L* - *i*) - *L* + *gcd*(*i*, *L*)] = *L*2 - 2*iL* + 2*i*2 - 2*L* + 2*gcd*(*i*, *L*) 65 66 Firstly, we enum *L* from 1 to *min*(*N*, *M*). Then the task is to calculate .  can be calculated by the following steps: 67 68 1. Enum all of the divisor *k* of *L* and the task is to calculate the count of *i* where *gcd*(*i*, *L*) = *k*. 69 2. The count of *i* where *gcd*(*i*, *L*) = *k* equals to φ(*L* / *k*). 70 71 Finally, . 72 73 If there are multiple queries, we can calculate the prefix sum of ,  and , then we can answer each query in *O*(1).