These two strings must have the same length. Then, we compare them letter by letter and find out all the indices of different letters. The number of difference must be exactly two and we check whether they satisfy a simple swapping rule.
The problem requires extremely precise results and thus we should try to only use integers to handle all the calculation.
At first, we determine for each player that he should use a first or b first. For convenience, we assume that a > b, and we should check which one of 
and 
is larger. We can rewrite as 
, and thus it is sufficient to compare their numerators to determine which one has a larger value. Similarly, sorting should also be implemented in this manner, i.e., we only compare their numerators. Finally, when we output , it is equivalent to the problem of printing the result of x / 100 for some positive integer x, with a precise decimal place. We can transfer x into a string and insert “.” at the correct position.
I know two methods to solve this problem.
1) After some observation, one can find that for the n-th figure, the number is 
.
2) We use an and bn to denote the number of upward and downward triangles, respectively, in the n-th figure. The recursive formula is an = 3an - 1 + bn - 1 and bn = 3bn - 1 + an - 1. By substituting the formula of bn into the latter equation, we have an + 1 - 6an + 8an - 1 = 0. This type of recursive equation has a solution of pattern as an = Axn + Byn, where A, B are constants while x, y are the roots of equation z2 - 6z + 8 = 0 (I forget how to prove this but it is done in this way). Therefore, we have x = 2, y = 4 and thus a1 = 2A + 4B = 3 and a0 = A + B = 1, and one can compute the final result.
This is a mathematical problem and we solve it by using Lagrange Multiplier method.
At first note that the optimal answer must satisfy x + y + z = S since if x + y + z < S, we can always increase x, y or z by S - (x + y + z) and we will obtain a better result.
According to Lagrange Multiplier method, we have
Unable to parse markup [type=CF_TEX]
. The left work is to implement partial derivative and solve the equation. The conclusion is that
, 
, 
. If a = b = c = 0, the answer can be x = 0, y = 0, z = S.We can consider that all the oats in the first layer are sorted just in the given order, and when they fall down to the deeper layers, they still keep the same order. From this perspective, we can say that the first layer divides the given n oats into n segments, and the second layer divides then into n - 1 segments while the third layer divides them into n - 2 segments, and so on.
Based on the above arguments, we can use dp[i][j][l][r] to denote the maximum weight that can “appear” in layer i, scale j, if all the oats within the interval [l, r] fall into this scale (or segment). The recursive formula is dp[i][j][l][r] = maxm = l - 1, l, l + 1, ...r(dp[i - 1][j][l][m] + dp[i - 1][j + 1][m + 1][r]), but note that if dp[i][j][l][r] < w[i][j], then dp[i][j][l][r] should be set to zero. The reason is that as no oats can fall down further from this scale, it is equivalent to saying that there is no oat left in this scale.
It seems that there is something wrong with the test case...
I solve this problem based on tutorials.
We can prove that the common divisor of these terms is either 1 or 2 (the proof in tutorials is quite clear). But this does not work when p = 2. For p = 2, the answer is straightforward, since for odd k, k2l + 1 is even and their LCM must be even, which gives an answer 0, while for even k, k2l + 1 is odd and their LCM must be odd, giving an answer equal to 1. For the following arguments, we only focus on p > 2.
If k is an even number, then k2l + 1 is an odd integer and all the terms must be co-prime. Thus, the LCM is simply their product. When k is an odd number, k2l + 1 is even and thus their LCM is their product divided by 2r - l.
The left main issue is to compute the product, which can be represented as Q = (k2l + 1)(k2l + 1 + 1)(k2l + 2 + 1)...(k2r + 1), and (k2l - 1)Q = k2r + 1 + 1. Thus, 
, and we should compute the inverse of k2l - 1 based on module p. According to fermat's theorem, if 2l%(p - 1) = t and k is not a multiple of p, then k2l%p = kt%p. Nevertheless, even if k is a multiple of p, the result is also correct since kt%p still gives zero. After obtaining r = k2l - 1%p, we can calculate its inverse by using fermat's theorem again. Be careful that r might be zero (it has no inverse), and for this case, it means k2l ≡ 1modp, and thus k2l + 1 ≡ 1modp and for any j ≥ l, we have k2j ≡ 1modp. Therefore, the product is equal to 2r - l + 1%p.
Finally, I have to say that this is a really difficult and complicated mathematical problem, involving quite many details and corner cases.
Comments (0)
