A. Autocomplete

We can enumerate all the given strings, and for each one that has the required beginning, we select the lexicographically minimal one as the answer.

B. Blog Photo

The problem requires that at least one of the sides should have a length of form 2^n. Thus, we can first let the length of height have a form of 2^n,2^(n-1),...,2^0, where 2^n should be no larger than h. For each height=2^i, we calculate the largest length of width so that it will not exceed the given w and meanwhile the area can achieve the maximum value. Next, we let the length of width have a form of 2^n,2^(n-1),...,2^0, and calculate the height in a similar manner.

As an example, we investigate how to calculate the width, denoted as W, given that the current length of height is H=2^i. Due to the constraints, we have 0.8<=H/W<=1.25, which means that H/1.25<=W<=H/0.8. As both the height and width are integers, one might use ceil(H/1.25)<=W<=floor(H/0.8) to obtain the values that W can take. However, this may lead to some unexpected precision problem. In fact, we can completely avoid this problem by using the "integer division" and "integer module" operations.

We can solve a more general problem, which gives two decimal numbers a and b (like 0.64, 0.2347, etc.) and an already known integer X, and we are asked to find out the exact range of values that another integer Y can take with the constraints that a*X<=Y<=b*X. We first transform a and b into a fractional form, i.e., a=p/q, b=s/t. Note that this is always possible. For instance, we can transform 0.2347 into 2347/10000, and the fractional form does not have to be irreducible. Then, we also transform the original constraints into

p*X/q<=Y<=s*X/t

Therefore, floor(b*X)=s*X/t, where the '/' in s*X/t is an "integer division" operation. For p*X/q, if (p*X)%q==0, we can directly use p*X/q as the lower bound, where '/' in p*X/q is an "integer division" operation, too; otherwise, ceil(a*X)=p*X/q+1, where '/' in p*X/q is still an "integer division" operation. In summary, the upper bound is s*X/t while the lower bound is ((p*X)%q==0?p*X/q:p*X/q+1).

Now, we go back to the original problem. As we still have another constraint 1<=W<=w, if ceil(H/1.25)>w, it means that we cannot obtain a reasonable value for the width; otherwise, the maximal value of width is just min(w,floor(H/0.8)). After we obtain the width, we first compare the area and then the height, and select the answer carefully as the problem requires.

C. Little Frog

For the given n integers 1,2,3,...,n, we can immediately find out that the absolute difference between any two integers is at least 1 while at most n-1. The problem asks to arrange the n integers in an appropriate order Q so that the absolute difference between any two neighboring integers should not be the same. Note that we will have n-1 absolute differences, and if they are all different from each other, they have to be exactly S={1,2,3,,,n-1}.

Note that the absolute difference can be at most n-1, which is achieved if and only if 1 is next to n or n is next to 1. Therefore, we can first set Q=(1,n) and S is reduced to S={1,2,3,,,n-2}. Similarly, one can check that to obtain the absolute difference n-2, we have to put 2 next to n, which gives Q=(1,n,2) and S is reduced to S={1,2,3,,,n-3}. Again, we deal with the absolute difference n-3, and one can find that Q=(1,n,2,n-1) and S is reduced to S={1,2,3,,,n-4}. In summary, we deal with S in a decreasing order, and when S is reduced to empty set, we will have obtained the required sequence Q.

D. Physical Education

This is like Selection Sort. We start from the first value of a and check whether it is the same as the first value of b. If they are the same, we move to the second one; otherwise, we enumerate array b from the second value and find out the one at some position j that is the same as the first value of array a. Then, we swap the value at position j with the second one. The swap is implemented like Bubble Sort, and the process should be recorded as part of the final answer. Similarly, we deal with the other values one by one, and will finally obtain the required answer.