374A — Inna and the pink pony

Lets find a solution for shifting a candy from the position (x₁, y₁) into position (x₂, y₂). On each step we shift (increase or decrease) x₁ by a and y₁ by b.

It is not difficult to understand that if |x₂ - x₁| is not divisible by a and |y₂ - y₁| is divisible by b answer doesn't exist.

We should also note that |x₂ - x₁| / a and |y₂ - y₁| / b Should be both even or odd as shifting is performed at a time for both values.

We should also look up for a corner case when step dropes us out from the board.

Now we can determine the way from (x₁, y₁) to (x₂, y₂) as max(|x₁ - x₂| / a, |y₁ - y₂| / b).

Lets calculate it for all corners and choose minimum or determine that the answer doesn't exist.

374B — Инна и девять

We can divide the task into subtasks because if two adjacent digits have sum none-9 the number transformation doesn't depends on other side relatively to the position between this two digits. It means we should divide our task into subtasks of kind: x or xyxyxyx...xyxy where x + y = 9. We should multiply all such answers because we are looking for the whole number of variants.

For x answer is 1. What should we do for xyxyxy? Let its length is s. Then if s is even we simply receive s / 2 nines. If s is odd one digit (any of them) will stay. Thus each sequence xyxyxyxyx...xyxyxy with odd length s increases the answer IN s times.

374C — Inna and Dima

Our task is tranformed to the task of finding cycle or maximal way, but lets solve it without any graphs.

Lets run dfs from each digit D, memorizing all already calculated tasks. If we come into the cell we have already been (in one of the previous D) than we should simply add the maximal way length to our current length. Way length is increased not in each cell but only when we come into A. If we come into the cell we have already been on current step (in our dfs running) this is the cycle and we should stop the algorithm. Don't forget to change the color of cell after droping from recursiong because you will receive "false cycle". Simply set the colour to current when come into the cell but decrease it before end of recursion for this cell.

374D — Inna and sequence

Lets note that not more than n numbers, thus it will be not more than n dropings. We will run this process using data structure Segment Tree (you can use another structures). Lets calculate the number of numbers in current segment. When the number is added we should simply go down from the root to the leaf and increase value for each segment on the way by 1. Deletetion — vice versa. If there is enough numbers in the left subtree we should go into the right one, othervise — into the left one. Don't forget to shift the a_i position by decreasing on i as all numbers are droped immidiately. And don't forget to break the cycle as soon as you reach first a_i such that there is no number to be droped out from it.

374E — Inna and babies

We will make the binary search to find the answer. For each time let's generate our segments and rotate them to transform them into horizontal and verticle. We can use transformation (x, y) to (x + y, x - y). Don't forget to make the union of all segments which were at the one diagonal and have an intersection. You should sort all segments of one type and iterate through them updating the size of the segment. Now we should only determine if there is at least one rectangle. For example we can iterate each verticle segment updating the set of all horizontal which begin not later than our verticle. For each verticle (the left one) we should iterate the right verticle and now calculate the set of horizontal which not only begin not later than the left verticle but also don't end earlier than the right one. Now we should only determine is ther is two or more horizontal segments from the set which satisfy also y-conditions for current vertical.