SummerSky's blog

By SummerSky, 7 years ago, In English

A. Sleuth

Be careful that only the last letter rather than the last character that determines the answer. Therefore, we can scan the string from the last character to the first one, and stop immediately when a Latin letter is met.

B. Sum

At first, we find out the largest digit that has appeared in the two integers, and denote it as B. Thus, the base must be strictly larger than B. If we want to achieve a longer length of the sum, the only hope is that the carry at the most significant position can be "1" but not "0", which in fact implies that the base should be too large. Therefore, we can just adopt B+1 as the base, and the following work is to simulate the operations of adding up the two integers. If the carry at the most significant position is "1", the answer will be the longest length of the given two integers plus by 1; otherwise it is just the longest length of the two integers.

C. Disposition

The description of the problem seems a little bit difficult to understand. It actually asks that to arrange integers from 1 to n in an appropriate manner so that the total number of such pairs, a[i] and i, which are relatively prime, are as many as possible, where a[i] denotes one of the integers from 1 to n. A simple solution might be a[n] = {n, 1, 2, 3,...,n-1}, and one can check that all the pairs a[i] and i are relatively prime (note that the index i starts from 1 but not 0).

D. Game

For this problem, it seems a little complicated to figure out how to select two neighbouring cells at each step. However, if we start from the final state and consider what should be done to move from the initial state to the final one, the solution is straightforward.

As the final sequence cannot have any two neighbouring cells that are both 0 or 1, there are only two feasible candiate sequences, i.e., 01010.... and 101010.... Therefore, we first assume that s[0] is correct, and then we alter the following values to satisfy that s[2i]=s[0] while s[2i+1]=(s[0]+1)%2, and meanwhile count the number of operations as C1. Be careful that we can only alter one cell if and only if at least one of its two neighbouring cells have the same value. Thus, it is likely that the target state (or sequence) cannot be achieved. Similarly, we next assume that s[0] is not correct, and then the following values should be changed so that s[2i]=(s[0]+1)%2 and s[2i+1]=s[0] hold, and count the number of operations as C2. Finally, we calculate min(C1,C2) and output it as the answer.

  • Vote: I like it
  • -3
  • Vote: I do not like it