Given three elements, we can generate all the 6 permutations, and calculate the distance to check which type it belongs to. Note that the distance might be a negative integer and when this occurs, add 12 to convert it to a positive one.
When given an uppercase letter, the basic idea is to enumerate the distance of all the feasible combinations of “Shift” and the corresponding lowercase letter, and check whether there exists any one that satisfies the requirement. However, if we implement the computayion every time the query comes, it may lead to TLE. As there are at most 26 uppercase letters, we can first calculate the distance for each one, and store the results. When a query comes, just take out the corresponding result.
This problem can be solved by direct simulation. Suppose that a < b, and one can see that after time 
, the two trains meet each other again, and thus it is sufficient to focus only on this time interval.
We implement the simulation based on the length of b, i.e., we first consider the time interval [0, b], then [b, 2b], [2b, 3b], and so on. There are exactly 
such intervals. Next, we store and update the starting time of train-a in each interval of length b, and calculate the number of interval of length a that is included. This total length is just the time that train-a will be selected, while the left length belongs to train-b.
The total complexity is about O(max(a, b)).
This problem can be solved by straightforward implementation. The key point is to store the number of “*” and “&” for each type and do not forget the case where the type reduces to “errtype”.
This is a famous game theory problem, referred to as Sprague-Grundy Theorem. One can check the book written by the great master Competitive Programmer's Handbook — a new book on competitive programming for more details.
Comments (0)
