pleasurepain's blog

By pleasurepain, 8 days ago, In English,

A. Spit Problem

For a camel with given parameters x[i] and d[i], he (or it) can hit at position x[i]+d[i] according to the problem. As the number of camels is at most up to 100, it is feasible to check for any two camels whether they can hit each other or not.

B. Traffic Lights

When the car arrives at the traffic light, if it is green, then the car can move on as if there were no traffic lights; while if it is red, the car has to wait until the light turns to be green, and then it can reach the destination. Therefore, the key point is in fact to determine whether the car has to wait or not, and if yes, how much time should it wait for.

We can take the total time that green light and red light lasts as an entirety (or a cycle), i.e., t=g+r, and then we should find out at which cycle does the car reach the traffic light. At first, we compute k=d/((g+r)*v), where "integer division" is adopted. The value of k means that when the car reaches the traffic light, it takes at least k cycles. Then, the problem can be solved based on the following two cases:

1) (g+r)*v*k<=d && d<(g+r)*v*k+v*g: this means that when the car arrives at the traffic light, it is green, and thus the car can directly pass the light and the total time is l/v (mathematical division, or 1.0*l/v);

2) d>=(g+r)*v*count+v*g: this means that when the car reaches the traffic light, it is red, and the car has to wait for (g+r)*(k+1)-1.0*d/v, and therefore, the total time is (g+r)*(k+1)-1.0*d/v+1.0*l/v.

C. Mail Stamps

The indices of cities are integers from 1 to 10^9, which makes it difficult to directly deal with since the indices are too large. Thus, we can adopt a 'map<int , int>' (Standard Template Library in C++) to reduce the indices to a smaller range, i.e., from 1 to 10^5, due to that n is up to 10^5. Whenever a city is processed, we can use function ".find(key)" to check whether this index (or called key) has occurred before or not, if no, we can map this index to a smaller one. As ".find(key)" is implemented based on a binary search (perhaps a balanced binary tree), the complexity O(logN) is fast enough. Moreover, we should maintain another array reverse[n] to indicate the real index corresponding to the one after mapping, i.e., reverse[value]=key, to output the correct route.

After the above process, the left problem is relatively simpler. We can establish a graph, in fact a link, and implement a traversal from any starting city to obtain the route. The starting city can be found by checking the degree of each city after the graph is established. As the problem guarantees, there should be exactly two cities with degree one, and any one of them can serve as the starting city.

D. Ant on the Tree

This problem can be solved by directly visiting the leaf nodes in the requested order. At first, we can establish an adjacency matrix to indicate the connection relationship. Then, the nodes with degree one are leaf nodes (note that the root node may have degree one as well, and take care for this case). Then, we can implement a BFS (Breadth First Search) to generate another array parent_node[] which stores the parent node of any node. Specifically, the parent node of root node can be set to -1.

Next, we go to the first leaf node. This route just starts from the root node and ends at the leaf node, which is not difficult to find out. Then, we move from one leaf node leaf[i] to the next one leaf[i+1]. With the help of parent_node[], we can find the nearest common parent node of leaf[i] and leaf[i+1]. Then, the route first starts from leaf[i] and ends at this common parent node, and then moves on to leaf[i+1]. For the last leaf node leaf[k-1], the route starts from leaf[k-1] and ends at the root node. During the above process, we can count how many times one edge has been visited. If some edge has been visited for more than two times, then the answer is "-1"; while on the other hand, the requested route exists, and we can directly output the route that has been stored before.

  • Vote: I like it  
  • -9
  • Vote: I do not like it