A. Football

This is one feasible solution. We can use the "map<string, int>" provided by C++ to record the number of goals for each team. Moreover, we should also store the name of the two teams, i.e., the two strings (note that it is likely to have only one string appearing in the input). Then, we just compare the number of goals for each team and output the answer.

B. Letter

We can use "getline(cin,s)" provided by C++ to deal with a string containing blank space as input. We first deal with the input s1 and use the "hash" idea to record the number of letters that have appeared. Note that the blank space should not be considered as the problem requires. Then, we deal with the input s2 and similarly adopt the "hash" idea to record the number of letters appearing in s2. Finally, for each letter that has appeared in s2, we check whether s1 has provided enough such a letter or not.

C. Lucky Tickets

For an integer, it is divisible by 3 if and only if the sum of its digits is divisible by 3. A simple proof is that we write the integer as

A=a0*10^0+a1*10^1+...an*10^n

=a1*(10^1-1)+a2*(10^2-1)+...an*(10^n-1)+(a0+a1+a2+...an)

It is obvious that a1*(10^1-1)+a2*(10^2-1)+...an*(10^n-1) is divisible by 3 and thus the conclusion is straightforward.

Therefore, we can count the number of tickets that are divisible by 3 as x, and the number of tickets divided by 3 resulting in a remainder 1 and 2 as y and z, respectively. The answer is x/2+min(y,z), where "/" is integer division.

D. Journey

One can first prove that if both n and m are odd integers, we can definitely not return back to (1,1) without using any teleporter. The proof is based on painting colors. We first paint (1,1) with black and the next cell that we move to with white. Then, for the following steps, we just paint the cells with black and white in an alternative manner. As we visit each cell exactly once except for (1,1), this means that if we successfully achieve this goal, the last cell we reach must be painted with white color, which is contradictory with the fact that we have painted (1,1) with black color. Furthermore, we can always construct a feasible route for the case where at least one of n and m is an even number, and thus the solution can be summarized as follows:

1) Both n and m are odd integers. We start from (1,1) and visit all the cells in the first row and then the second row and so on. At last, we will always reach the cell (n,m), and by building a teleporter at cell (n,m) we can return back to (1,1);

2) At least one of n and m is an even integer. Without loss of generality, assume that n is an even number. We start from (1,1) and move on to (1,m). Then, we visit all the cells in the second row except for (2,1), i.e., we will reach cell (2,2). Next, we go to (3,2) and move on until we reach (3,m). In a word, we just visit the cells row by row but leaving the first column unvisited. Finally, we will surely arrive at (n,2). By visiting the first column, we just return back to (1,1) without using any teleporter.

Note that there exist several special cases. One case is (n=1, m>2), or (m=1, n>2). For this case, we have to build a teleporter at cell (n,m) and then can return back to (1,1). Another case is (n=1,m=2), or (n=2,m=1), where no teleporter is necessary.

E. Race

As both n is not quite large, we can count the number of "lead" for every two cars, which contributes O(n^2) complexity. For the i-th car and j-th car, we adopt two pointers pi and pj to enumerate (or scan) their time segments independently. Moveover, we adopt a "flag" to denote which car is leading over another one. We first find out the shortest time segment T for the current pi and pj, and use it to compute the current distance of the two cars. Then, we compare which car is leading over another one and update the number of "lead" accordingly. Finally, we should decrease the two time segments with T, and if any of them is reduced to zero, we just add pi or pj by 1 so that we move on to check the next time segment. As these operations will change the original values of time segments, we should backup them before implementing such operations so that when we deal with another two cars, the time segments are not "zero". By some simple amortized analysis, the total complexity is O(n^2*k).

I think for this problem, the most difficult step is how to "scan" any two time segments in an efficient and correct manner.