336.md (6217B)
1 Source: https://codeforces.com/blog/entry/8574 2 3 ## [336A - Vasily the Bear and Triangle](/contest/336/problem/A "Codeforces Round 195 (Div. 2)") 4 5 *val* = |*x*| + |*y*|. Then first point is (*val* * *sign*(*x*), 0), second — (0, *val* * *sign*(*y*)). Swap points if needed according to statement. 6 7 Let's see why this is the answer. Conditions *x* ≠ 0 and *y* ≠ 0 give us that one point is on X-axis, and the other on Y-axis. Let's see how it works for *x* > 0 and *y* > 0. Other cases can be proved in similar way. We need to show, that (*x*, *y*) belongs to our triangle(including it's borders). In fact (*x*, *y*) belongs to segment, connecting (*x* + *y*, 0) with (0, *x* + *y*). Line through (*x* + *y*, 0) and (0, *x* + *y*) is *Y* = - *X* + *x* + *y*. Using coordinates (*x*, *y*) in this equation proves the statement. 8 9 [Author's solution](http://pastebin.com/fNz05bHS) 10 11 ## [336B - Vasily the Bear and Fly](/contest/336/problem/B "Codeforces Round 195 (Div. 2)") 12 13 Also you could iterate circles, adding distance for each of them and dividing by *m*2 in the end. Let's see how the *i*-th iteration works 1 ≤ *i* ≤ *m*. Distance to *m* + *i*-th circle is 2*R*. Distance to *m* + *j*-th circle, where |*j* - *i*| = 1, is . For other circles it's quite simple to calculate sum of distances. There are *i* - 2 circles which located to the left of current circle. So, sum of distances for these circles is . In the same manner we can calculate answer for cirlcles which are located to the right of the current circle 14 15  16 17 [Author's solution](http://pastebin.com/iTr4213i) 18 19 ## [336C - Vasily the Bear and Sequence](/contest/336/problem/C "Codeforces Round 195 (Div. 2)") 20 21 Let's check max beauty from 29 to 0. For every possible beauty *i* our aim is to find largest subset with such beauty. We will include in this subset all numbers, that have 1 at *i*-th bit. After that we do bitwise *and* as in statement, and if the resulting value is divisible by 2*i*, then there is the answer. Solution works in *O*(*n*). 22 23 [Author's solution](http://pastebin.com/znNnQF1z) 24 25 ## [336D - Vasily the Bear and Beautiful Strings](/contest/336/problem/D "Codeforces Round 195 (Div. 2)") 26 27 *any* — random binary string, *s* + *g* — concatenation of strings, *MOD* = 1000000007. 28 29 String 1 + *any* always transforms into 0, string 1 — into 1. String 01 + *any* always transforms into 1, string 01 — into 0. String 001 + *any* transforms into 0, string 001 — into 1, and so on. Using these facts let's consider following solution. 30 31 Cases like strings without ones or zeroes are easy. For every *i* (in zero-based numbering) let's assume that it is position of the first occurence of 1 in our string. Using already known facts we can understand what is the final result of transformations for such string. If the result equals to *g*, we add *C*(*cnt*[0] + *cnt*[1] - *i* - 1, *cnt*[1] - 1) to the answer. Calculation of binomial coefficients is following: *fact*[*i*] = *i*!%*MOD*, , *C*(*n*, *k*) = *fact*[*n*]*inv*(*fact*[*n* - *i*]*fact*[*i*]), where *inv*(*a*) — inverse element modulo *MOD*. *inv*(*a*) = *a**MOD* - 2, because *MOD* is prime number. 32 33 [Author's solution](http://pastebin.com/2cZ2qefM) 34 35 ## [336E - Vasily the Bear and Painting Square](/contest/336/problem/E "Codeforces Round 195 (Div. 2)") 36 37 Pretty tough problem. Consider following DP *dp*[*lvl*][*op*][*cur*][*type*] — number of ways to take *op* triangles, if we have 2*lvl* + 1 squares. *cur*, *type* — auxiliary values. Answer will be *dp*[*n*][*k*][0][2]*k*!. *type* means type of transitions we make. *cur* — amount of used quarters (*cur* = 4 — 2 quarters, *cur* < 4 — *cur* quarters). It is important to distinguish *cur* = 2 from *cur* = 4, because amount of consecutive pairs of unused quarters is different. 38 39  40 41 About transitions. *type* = 2. Iterate amount of pairs (considering *cur*) of consecutive quarters that we will take. It is important for them to have no common quarters. We can get two pairs only in case *cur* = 0. Let's also take some quarters that are not in pairs. Calculate number of ways to select corresponding triangles and add to the current DP-state value *dp*[*lvl*][*op* - *choosen*][*newcur*][1] * *cntwaystochoose*. For better understanding of *type* = 2 check my solution (*calc*(*n*, *k*, *cur*, *type*) — *isfordp*[*n*][*k*][*cur*][*type*]). 42 43 *type* = 1. Now we take triangles at the borders (number of squares is 2*lvl + 1). "at the borders" means marked X, see the picture. 44 45  46 47 Iterate amount of pairs (considering *cur*) of consecutive triangles we take. It is important for pairs to have no common triangles. Let's also take some triangles that are not in pairs. Calculate number of ways to select corresponding triangles and add to the current DP-state value *dp*[*lvl*][*op* - *choosen*][*cur*][0] * *cntwaystochoose*. 48 49 *type* = 0. We take triangles at the borders (number of squares is 2*lvl). "at the borders" means marked X, see the picture. 50 51  52 53 Take some triangles, not in pairs. Calculate number of ways to select corresponding triangles and add to current DP-state value *dp*[*lvl* - 1][*op* - *choosen*][*cur*][2] * *cntwaystochoose*. Starting values: *dp*[0][0][*cur*][1] = 1, *dp*[0][*cnt*][*cur*][1] = 0, *cnt* > 0. 54 55 [Author's solution](http://pastebin.com/z7zNRXHT)