Блог пользователя SummerSky

Автор SummerSky, 8 лет назад, По-английски

A. Flea travel

Suppose that at first the flea is at position S. According to the problem, the flea will appear at position

(S+1+2+3+...+t-1)%N=(S+(t-1)*t/2 )%N

after the t-th minute. It seems that we have to check infinite times to find out whether it can appear at all the positions, which is in fact impossible. However, we can prove that if the flea is at position V after the t-th minute, then it must return to position V after the (t+2*N)-th minute. The proof is

(S+(t+2*N-1)*(t+2*N)/2 )%N=(S+(t-1)*t/2+(t-1)*N+t*N+2*N*N)%N=(S+(t-1)*t/2 )%N

Therefore, it is sufficient to check from 0-th minute to (2*N-1)-th minute, and then we can find out whether the flea can visit all the positions or not.

B. Smallest number

We can generate all the feasible permutation of the given four integers, and denote the them as a,b,c,d. Furthermore, we denote the operations as x,y,z. Then, we can first calculate ((a x b) y c) z d, and then calculate ((a x b) z (c y d)). For all the results that we have obtained, it is sufficient to record the minimum one and this is just the answer.

C. Pie or die

A problem that is full of tricks...

For the i-th pie, we can calculate its Manhattan distance to the four borders. Among the four Manhattan distances, we only focus on the minimum one, denoted as d[i], and the corresponding border is denoted as B[i]. Furthermore, we select the pie which has the minimum distance d[i], and this distance is denoted as D while the corresponding border is B. Then, we consider the answer based on the value of D.

1) D=0: the answer is obviously yes;

2) D=1: the answer is yes; one simple strategy is to first move one step closer to border B; if this position is not blocked, then we win; otherwise we move on to the corner along the border (we can choose any corner); as the corner in fact "provides" two "exits" to escape from the board, the two "exits" cannot be blocked at the same time;

3) D=2,3,4: the answers are all yes; the strategy is that we always first try to move to the border B and then move on along the four borders until we find a corner with two "exits" which cannot be blocked at the same time; it is guaranteed that if D<=4, there is always a corner that has two "exits" and they cannot be blocked at the same time, which can be proved as follows:

Note that it takes us four steps to reach the border B. The competitor can take advantage of these four steps to block one "exit" (or edge) for each of the four corners. However, this means that when we arrive at the border, we can successfully escape since only the "exits" at the four corners have been blocked. If the competitor only blocks one "exit" (edge) for some (not all) of the four corners, we can move on along the border B and will finally arrive at the corner which has two "exits".

4) D>=5: the answer is always no; the reason is that before we arrive at the border B, at least one of the "exits" (edges) at the four corners have been blocked; thus when we arrive at border B, the competitor can just block the edge that we are facing to, and even when we reach the corner, there exists only one "exit" and the competitor can always block it immediately after we arrive there.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится