For each x from 1 to 5000 store a list L(x) of such indexes i that ai = x. Then just check that all lists have even size and output the elements of each list in pairs.
One of the possible solutions is: for each Olympiad find the period of the preparation. This can be done by iterating the days back from the day of the Olympiad. For each day d of the preparation add pi to the number of distinct jury members that have to work on problems on day d. Then the answer is maximum calculated sum over all days. Be careful with the year 2012.
Lets denote the number of character x in s by Cs(x). Similarly Ct(x) is defined. Then the minimum number of changes required to get anagram of t from s is equal to 
. Now we need to obtain lexicographically minimum solution. Lets iterate through the positions in s from the left to the right. For a fixed position, look through all characters from 'a' to 'z' and for each character decide whether the optimal answer can contain this character in that position. If it can, put this character in that position and continue with the next position. To check if the given character is suitable quickly, we maintain the values Cs(x) and Ct(x) while iterating through positions.
. Now we need to obtain lexicographically minimum solution. Lets iterate through the positions in s from the left to the right. For a fixed position, look through all characters from 'a' to 'z' and for each character decide whether the optimal answer can contain this character in that position. If it can, put this character in that position and continue with the next position. To check if the given character is suitable quickly, we maintain the values Cs(x) and Ct(x) while iterating through positions.
Choose arbitrary rat (for say, the leftmost of the upmost). It's cell should be cleared. Make a BFS that never goes further than d from this cell (we will call such a BFS by d-BFS). It will visit approximately 2d2cells in the worst case. So, we have to blow the first grenade in one of the visited cells. Lets check every visited cell as a candidate. Make a d-BFS from the candidate cell. Some cells with the rats will not be visited. That means that they should be cleared by the second grenade. Choose arbitrary cell with a rat that was not cleared by the first grenade. Make a d-BFS from it. All cells visited by this BFS are candidates to blow the second grenade. Lets check every such cell. Checking a cell again means making a d-BFS from it. If this BFS visits all cells that were not cleared by the first grenade, that we have found a solution. As every d-BFS visits at most 2d2, the overall number of steps is approximately 8d6.
The problem can be solved by dynamic programming: denote as D(n, r) the maximum rating that we can achieve in the first n days with the condition that we have r kilos of food remaining from the day n - 1. It is obvious that if we decide to feed k friends on some day, the better way is to feed k friends with the lowest fj (of course we consider only friends that live with Vasya on that day). So we need to sort all available students in the order of increasing fj and try to feed 0, 1, 2, ldots first students in this order. We have 4002 states and 400 transitions from each state.
Không có nhận xét nào:
Đăng nhận xét