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 *a*_{n} and *b*_{n} to denote the number of upward and downward triangles, respectively, in the *n*-th figure. The recursive formula is *a*_{n} = 3*a*_{n - 1} + *b*_{n - 1} and *b*_{n} = 3*b*_{n - 1} + *a*_{n - 1}. By substituting the formula of *b*_{n} into the latter equation, we have *a*_{n + 1} - 6*a*_{n} + 8*a*_{n - 1} = 0. This type of recursive equation has a solution of pattern as *a*_{n} = *Ax*^{n} + *By*^{n}, where *A*, *B* are constants while *x*, *y* are the roots of equation *z*^{2} - 6*z* + 8 = 0 (I forget how to prove this but it is done in this way). Therefore, we have *x* = 2, *y* = 4 and thus *a*_{1} = 2*A* + 4*B* = 3 and *a*_{0} = *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*] = *max*_{m = 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*, *k*^{2l} + 1 is even and their LCM must be even, which gives an answer 0, while for even *k*, *k*^{2l} + 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 *k*^{2l} + 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, *k*^{2l} + 1 is even and thus their LCM is their product divided by 2^{r - l}.

The left main issue is to compute the product, which can be represented as *Q* = (*k*^{2l} + 1)(*k*^{2l + 1} + 1)(*k*^{2l + 2} + 1)...(*k*^{2r} + 1), and (*k*^{2l} - 1)*Q* = *k*^{2r + 1} + 1. Thus, , and we should compute the inverse of *k*^{2l} - 1 based on module *p*. According to fermat's theorem, if 2^{l}%(*p* - 1) = *t* and *k* is not a multiple of *p*, then *k*^{2l}%*p* = *k*^{t}%*p*. Nevertheless, even if *k* is a multiple of *p*, the result is also correct since *k*^{t}%*p* still gives zero. After obtaining *r* = *k*^{2l} - 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 *k*^{2l} ≡ 1*modp*, and thus *k*^{2l + 1} ≡ 1*modp* and for any *j* ≥ *l*, we have *k*^{2j} ≡ 1*modp*. Therefore, the product is equal to 2^{r - 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.