296A — Yaroslav and Permutations

Note that after applying the operations of the exchange, we can get any permutation of numbers. Not difficult to understand that the answer is "YES", if you can place a single number that it would not stand in the neighboring cells. Thus, if a some number is meeted C times, it must fulfill the condition C <= (n +1) / 2. 296B — Yaroslav and Two Strings We solve the inverse problem: count the number of ways to make comparable pair. To start count the number of ways to make the first line of less than equal to the second. This number equals the number of ways to do this for each item individually as they are position independent. Let's count the same amount, but when the second line-less equal to the first. And similarly to count the number of ways to make two lines equal. For each character values ​​can be considered as a simple cycle. Now we take the value of 10 to the number of question marks in the input file and subtract the answer to the inverse problem, it will be the answer. 295A — Greg and Array In order to add the value of d in the interval [x, y] is sufficient to have an array of values ​​of b and put b [x] + = d b [y +1] — = d Next in a single pass through the array of easily reduced the numbers. We apply this method twice: first for the query, and then operations (knowing how much time we will fulfill it.) 295B — Greg and Graph

To solve the problem, we must thoroughly understand the principle of the Floyd algorithm. A general view of the Floyd algorithm: for (k = 1; k <= n; k + +) for (i = 1; i <= n; i + +) for (j = 1; j <= n; j + +) a [i] [j] = min (a [i] [j], a [i] [k] + a [k] [j]); That is, at each step, we try to flow the way across the top of K. We will not remove the top, and add (going from the end). At each step, we will try to flow the way between all the nodes through the new. Thus we get a solution that works in cubic time. 295C — Greg and Friends

Note that at each step we are interested in only the position of the boat (number of banks) and the number of people 50 and 100 weight on each shore. With that number of people on one side is completely determined by the other. To find the minimum number of crossings will be used wave algorithm based on this condition. To find the number of ways to add just the sum of all transitions in the state transition will move all the way from one state to another by multiplying the number of ways to choose the people who need to move from one state to another. 295D — Greg and Caves

We use the dynamic programming: dp [i] [j] — how many ways there are to construct a figure that the line will be exactly i j columns of black cells are occupied, and everything in between. In this case, the shape should not decrease (in other words, we take only the upper part of the figure). How to make the transition? Note that dp [i] [j] = 1 + dp [i-1] [2] * (j-1 2) + ... + Dp [i-1] [l] * (j-l +1) + ... + Dp [i-1] [j]. We rewrite it: dp [i] [j] = 1 + dp [i-1] [2] * j + ... + Dp [i-1] [l] * j + ... + Dp [i-1] [j] * j — dp [i-1] [2] * 1 — dp [i-1] [3] * 2 — ... — Dp [i-1] [j] * (j-1). Clearly, if the make partial sum, the data value is considered as very simple. How to calculate the full response: we will sort out the maximum number of suitable t (indicated in the condition). Now, the only difference is that the following line should contain strictly fewer columns. That is, we have a similar transition, with -1 term. Also note that fixing the "foundation" we must multiply the number of ways for a number of ways to place it on the plane, that is the basis of width j, we can put (m-j +1) ways. 295E — Yaroslav and Points

Learn how to solve the problem of finding the sum of the distances between points. If paint, what happens when you add one point, then we get the formula: x_i * (2 * in) Where x_i — sorted coordinates, and n is the total number of points. Let us learn to know the answers to the two segments of points to know the answer to their association. It is clear that for the calculation of such information need only add two response and adding the sum of the first coordinate set multiplied by a certain number, and and add the sum of the second set of coordinates multiplied by some, perhaps another number. Thus knowing the answers to some segments of the overall response. We will use the root decomposition or Cartesian tree for the storage of such segments. It is not difficult to understand that the insertion and deletion is done quickly enough for these structures. For example, for the root decomposition can be every time just cut and paste the desired point in the intervals, and if the set was contain long stretches or many segments, then simply reconstruct it again. Asymptotics of the solution does not change.