For the given string, if its length is not larger than 10, we shloud output it directly; otherwise we should output the first letter, the length minus 2, and the last letter.
It can be observed that a reasonable answer must always be writen as x*k+y, where x denotes the number of values that are equal to k while y denotes the unique value which is neither k nor zero. Note that y can be zero.
According to the conditions, we have (x*k)/(n*k)≤(t/100), and thus x≤t*n/100. We can first compute x as t*n/100, where "/" denotes the integer division. Then, we can enumerate y from 0 to k-1, inclusively, to find out the answer.
It seems that we have to enumerate all the feasible polygons and their rotation angles to find out the answer, which leads to complexity of O(N^2). However, one can check that if a polygon with M edges is found to be reasonable, then we can always find at least another one polygon with Q edges, where Q is a divisor of M, which is reasonable as well. The reason is simple. As all the M points are reasonable, we can select the first points of every M/Q points to form the target polygon.
Therefore, it is sufficient to test the polygons which have 3, 4, 5, 7, 11, 13... edges. It can be seen that all the integers are prime except for 4. The left work is to find out all the prime numbers from 3 to the given n. There exists a famous algorithm with complexity O(NlogN), and one can search on the internet for more details. I remember that the number of prime integers from 1 to some constant N is O(logN). If I am correct, the total complexity turns out to be O(NlogN).
The solution is straightforward, and one should just follow the steps to calculate the results. However, the coding is fairly complicated....
This is a nice problem to practice DP based on bitmask technique.
We use an integer i from 0 to (1<<n) to denote the "states". For a bit, "1" means that the corresponding element is used to generate a new element; while "0" means that it has not been used. At the first step, for each state, we take out "1"s and calculate the sum weight that it can achieve. Moreover, for each sum, we store all the states that can achieve this value. Then, we use dp[1<<n][k] to denote that whether it is possible or not to generate the first several target elements, while achieving the corresponding states. The 0-th column of dp is initialized to zero except for the first row, which is set to 1 to indicate that it is possible to generate 0 target element while achieving the all-zero state, i.e., no given elements are used. Then, to update dp[row][col], we first enumerate all the values of dp in column col-1, and find out those with dp[row'][col-1]=1, since only these states are reasonable. Next, we enumerate all the states S that can generate the col-th target element. Note that only those satisfying S & row'=0 should be considered as reasonable states, and this in fact leads to a new state S | row', and thus we should update dp[S | row'][col]=1. Furthermore, we should keep S so that we can backtrace the equation required by the problem.
Comments (0)
