A. Worms Evolution

As n is at most as large as 100, we can adopt a nested-3-loop to find out the answer, i.e., we enumerate all the possible positions of i, j and k in turn, and check whether the condition a[i]=a[j]+a[k] can be satisfied or not. One more thing to notice is that i, j and k should be three distinct integers.

B. Sysadmin Bob

This problem is not quite difficult but one should be very careful.

At first, notice that if '@' appears at the first position or the last position, the answer will be "No solution". Then, if there exist any two successive positions i and i+1 with s[i]=s[i+1]='@', the answer should be "No solution" as well. Except for this, if one can find out two positions i and i+2 with s[i]=s[i+2]='@', it also results in "No solution". Finally, if no '@' can be found, the answer is still "No solution".

After excluding the above cases, all the other cases should have reasonable answers. Without loss of generality, once we have reached the first letter following '@', we can immediately add ',' to obtain a reasonable solution. However, there is one exception, i.e., no ',' shoulbe be added after the last '@'.

C. Schedule

At first, we can sort the groups in an increasing order of the starting time of their lessons. Then, we enumerate the groups from the first one to the last one, and for each group, we check whether it is possible to achieve the state where no two time periods of lessons intersect by deleting this group. The test can be simply implemented by comparing the i-th group and (i+1)-th group, for every feasible i. In other words, we check whether the finishing time of group i is later than the starting time of group i+1, and if all the pairs lead to answers "NO", then it means that the remaining groups can achieve the state at which no two time periods of lessons intersect.

D. Chocolate

I solve this problem by using a divide-and-conquer technique. I also find that many people solved this problem based on DFS. But I do not quite understand the principle behind this idea. It would be very nice if anyone can shed some light on this idea...

I adopt an array perpendicular[x1][y1][y2] to denote that there is a line with two ends (x1,y1) and (x2=x1,y2). Similarly, I use another array parallel[y1][x1][x2] to denote a line with ends (x1,y1) and (x2,y2=y1). Then, we can start with the whole plane, i.e., (x1=0,y1=0,x2=W,y2=H), and try to calculate the areas, which consists of the following three phases:

phase 1): enumerate x from x1+1 to x2-1 (note that x1 and x2 are not included since the problem guarantees that the plane is cut into two pieces which are not empty) and check whether perpendicular[x][y1][y2]=1 or not. If perpendicular[x][y1][y2]=1, it implies that the current considered piece is cut into at least another two pieces since there is a line with two ends (x,y1) and (x,y2). Thus, we can divide it into two subproblems (x1,x,y1,y2) and (x,x2,y1,y2);

phase 2): enumerate y from y1+1 to y2-1 (similar reasons as above), and check whether parallel[y][x1][x2]=1 or not. If parallel[y][x1][x2]=1, it means that the current piece is cut into at least another two pieces by a line with ends (x1,y) and (x2,y). Thus, it can be divided into two subproblems (x1,x2,y1,y) and (x1,x2,y,y2);

phase 3): no lines cut the current piece and it stays as it is. We can directly calculate the area by (x2-x1)*(y2-y1), which is referred to as "conquer".

Finally, we sort the areas as the problem requests and output them.

E. TV Game

This problem can be solved by adopting a dynamic programming technique. We use F[x][y] to denote that for the first x+y digits, x of them are taken by person H while y of them are taken by person M, and the value of F[x][y] is the maximum sum that can be achieved. Suppose that by giving the (x+y)-th digit to H will increase the sum by number(x+y,H) while giving to M leads to an increment number(x+y,M). Then, F[x][y] is only determined by F[x-1][y] and F[x][y-1]. In detail, F[x][y]=MAX(F[x-1][y]+number(x+y,H), F[x][y-1]+number(x+y,M)). F[][] is initialized by setting F[0][1]=number(1,M) and F[1][0]=number(1,H). When updating F[x][y], we should implement this process by increasing x+y from 1 to 2n, i.e., first update all F[x][y] with x+y=2, then x+y=3, and finally x+y=2n. To record the digits taken by H and M, we can further introduce another array R[x][y], which is initialized by setting R[0][1]='M' and R[1][0]='H'. R[x][y] is updated as F[x][y] is calculated, i.e., if F[x-1][y]+number(x+y,H)>F[x][y-1]+number(x+y,M), then we have R[x][y]='H'; otherwise R[x][y]='M'. Finally, we start with F[n][n], also R[n][n], and backtrack until F[0][0] is reached. This can be implemented by comparing F[x-1][y]+number(x+y,H) and F[x][y-1]+number(x+y,M), and then we know which one to backtrack.