117A - Elevator

At first, note that it takes 2m - 2 minutes for the elevator to go up from the first floor to the top and return back, and we refer to this event as a “cycle”. Thus, for each query, we can compute the floor on which the elevator stops at time t_i.

Now, the left work should be done very carefully. For instance, we should determine whether we can catch the elevator within the current cycle, or we have to wait for another cycle. Moreover, after we get into the elevator, we should determine whether we can reach the target floor within the current cycle, or wait for more one cycle.

117B - Very Interesting Game

If we denote the first and second integer as x and y, then the integer after concatenation can be represented as x × 10⁹ + y.

Thus, we should check whether 10⁹x%mod = (mod - y)%mod could hold or not. It is obvious that if b ≥ mod - 1, then the above equation can always be satisfied, since (mod - y)%mod can take any value from {0, 1, 2, ..., mod - 1}. If b < mod - 1, then (mod - y)%mod can only take values of {0, mod - 1, mod - 2, ...mod - b}. Therefore, we can enumerate x from 1 to mod - 1, and find the first (also the minimum) integer that can satisfy the equation. Note that it is not necessary to test any x that is larger than mod - 1.

117C - Cycle

If there is no cycle, then it is obvious that no cycles of length 3 exist. On the other hand, there must be at least one cycle of length 3.

We denote the cycle as a₁, a₂, ..., a_n, and check a₁, a_i, a_i + 1, where i is initialized with 2, and increased to n - 1. As this is a cycle, there is an edge from a₁ to a_i, and also en edge from a_i to a_i + 1. We obtain a length-3 cycle if there is an edge from a_i + 1 to a₁. However, if this edge is from a₁ to a_i + 1, then we increase i to i + 1, and check the next three nodes. This construction will always find out a tuple that achieves our target, since this is a cycle, and there must exist at least one node that has an edge directed to a₁.