val = |x| + |y|. Then first point is (val * sign(x), 0), second — (0, val * sign(y)). Swap points if needed according to statement.
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.
Also you could iterate circles, adding distance for each of them and dividing by m2 in the end. Let's see how the i-th iteration works 1 ≤ i ≤ m. Distance to m + i-th circle is 2R. 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
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 2i, then there is the answer. Solution works in O(n).
any — random binary string, s + g — concatenation of strings, MOD = 1000000007.
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.
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 + cnt - i - 1, cnt - 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) = aMOD - 2, because MOD is prime number.
Pretty tough problem. Consider following DP dp[lvl][op][cur][type] — number of ways to take op triangles, if we have 2lvl + 1 squares. cur, type — auxiliary values. Answer will be dp[n][k]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.
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] * cntwaystochoose. For better understanding of type = 2 check my solution (calc(n, k, cur, type) — isfordp[n][k][cur][type]).
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.
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] * cntwaystochoose.
type = 0. We take triangles at the borders (number of squares is 2*lvl). "at the borders" means marked X, see the picture.
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] * cntwaystochoose. Starting values: dp[cur] = 1, dp[cnt][cur] = 0, cnt > 0.