SummerSky's blog

By SummerSky, 6 years ago, In English

117A - Лифт

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 ti.

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 - Очень занимательная игра

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

Thus, we should check whether 109x%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 - Цикл

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 a1, a2, ..., an, and check a1, ai, ai + 1, where i is initialized with 2, and increased to n - 1. As this is a cycle, there is an edge from a1 to ai, and also en edge from ai to ai + 1. We obtain a length-3 cycle if there is an edge from ai + 1 to a1. However, if this edge is from a1 to ai + 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 a1.

  • Vote: I like it
  • +1
  • Vote: I do not like it