We can enumerate all the feasible division that divides the given sequence into three parts. For each part, we check whether it has leading zeros (be careful that “0” does not have leading zeros) and whether it exceeds 106.
Straightforward implementation solves this problen. It is suggested that when asked to compare a / b and c / d, one should equivalently check a × d and b × c.
The main idea is greedy algorithm. It is obvious that lower points should be assigned with smaller factors, and thus we should sort one array in an increasing order of points and another array in an increasing order of factors, and multiply them and add the results together.
Here are two issues that we should take care of. One is that the number of factors may be less than the total number of figures. In this case, we should append extra factors equal to t + 1 to the end of sorted factor array so that every point will have a corresponding factor. The second issue is that the factor array is given in a form of “prefix sum”, as p[i] denotes the total number of operations that we need implement in order to increase the factor value from 1 to i + 1, rather than the number of operations that we need to increase factor from i to i + 1.
At first, we need two tables, one for “us” and the other one for our rival, written as dp1[i][j] and dp2[i][j], to denote the probability that after the opposite player's i-th shot, the defensive side still has hp equal to j. These two tables can be computed based on techniques similar to pascal's triangle. In fact, both the two tables have infinite size, since it is possible that no shot pierce each other, and thus both the two players can survive as many rounds as they “want”. Nevertheless, it is sufficient to calculate the table to some finite round. The reason is that as long as the probability that one pierces the opposite player is not zero, the probability that one survives to the m-th round has some coefficient pO(m), which can be omitted compared with 10 - 4 if m exceeds some threshold. Tutorials suggest that this value should be 5000, while I think that 2000 is enough (perhaps I am wrong)...
Then, we define the “first event”, i.e., if we win, we win after the first shot, second shot, third shot, and so on. These events are independent with each other and thus we can compute each of them independently and finally add the results together. To win after the i-th shot, we should calculate the number of rival's shot before our i-th shot, and the probability that we survive can be directly obtained from the previously computed table. Furthermore, we should also calculate the probability that the rival survives after our (i - 1)-th shot but has hp = 0 after our i-th shot, which can also be directly queried from our table.
This problem inspires me that sometimes, instead of simulating two players alternatively, it is more convenient to focus on one player's behavior and check what happens after his move.
Comments (0)
