## Task A

This is pretty simple task - we have cycle and must direct all edges on it in one of 2 directions. We need to calculate cost of both orientation and print smallest of them.

There is a small trick - we can calculate cost of only one orientation and then cost of the other will be sum of costs of all edges minus cost of first orientation.

## Task B

Also very simple - we need literary do what we asked. We put all data in a map where for each pilot we have number of points and array of 50 elements - number of times pilot finished at corresponding place. Then we just need to find maximum in this array according to 2 given criteria.

## Task C

Reflection over 2 points is just a parallel shift for a doubled vector between them. So

*M*_{2n}=*M*_{0}because sequence of reflections may be replaced with sequence of shifts with doubled vectors*A*_{0A}_{2},*A*_{2A}_{4}, ...,*A*_{n - 2}*A*_{0}- and their sum is 0. So we can replace j with*j*' =*jmod*2*N*. Now we can just perform j' reflections. Suppose we need to find M' (x', y') - reflection of M(x, y) witch center at A(*x*_{0},*y*_{0}). Then*x*' = 2*x*_{0}-*x*,*y*' = 2*y*_{0}-*y*.## Task D

If robot is at last row then answer is 0. Suppose that for every cell of the next row we now expected number of steps to reach last row -

*z*_{i}. Let*x*_{i}be expected value of steps to reach the last row from current row. Then we have following system of equations:*x*

_{1}= 1 +

*x*

_{1}/ 3 +

*x*

_{2}/ 3 +

*z*

_{1}/ 3

*x*

_{i}= 1 +

*x*

_{i}/ 4 +

*x*

_{i - 1}/ 4 +

*x*

_{i + 1}/ 4 +

*z*

_{i}/ 4 for i from 2 to M - 1

*x*

_{M}= 1 +

*x*

_{M}/ 3 +

*x*

_{M - 1}/ 3 +

*z*

_{M}/ 3

This is tridiagonal system, it can be solved using tridiagonal matrix algorithm in linear time.

So we just have to solve this for each row starting from N - 1 and ending at i and then take x[j].

For M = 1 the answer is 2(N - i) because expected number of steps to go down is 2 - on each turn we either go down or stay

## Task E

At first we need to exclude answer -1. Answer is -1 if and only if first part of particles moves left and second part moves right (any of this parts may be empty)

Let's use binary search. Maximal answer is 1e9. Suppose we need to unserstand - whether answer is more then t or less then t. Let's itirate particles from left to right and maintain maximal coordinate that particle moving right would achive. Then of we will meet particle moving left that will move to the left of that coordinate in time t that we have 2 particles that will collide before time t. Otherwise we won't have such pair of particles.

Let's define function F(a,b) which returns X where X = 1 + X * a + (1-a) * b and e[i][j] is the expected number of steps that takes for robot to reach last row when robot is initially on cell(i,j).

Here is the whole code:

for (int i=1;i<=m;i++)

e[n][i]=0;

for (int i=n-1;i>=1;i--){

if (m == 1){

e[i][1]=f(1.0/2,e[i+1][1]);

}else{

for (int count=1;count<=30;count++){

e[i][1]=f(1.0/3,(e[i+1][1]+e[i][2])/2);

e[i][m]=f(1.0/3,(e[i+1][m]+e[i][m-1])/2);

for (int j=2;j<m;j++)

e[i][j]=f(1.0/4,(e[i][j+1]+e[i][j-1]+e[i+1][j])/3);

}

}

}

Let the origin Array to be A[1..m]..represents the previous Floor..then first put all elements in B to be zero.

then create Array C where C[i]=（B[i]+B[i-1]+B[i+1]+A[i])/4+1..then Let B=C and do it for many times can also calculate a new A...

" for (int count=1;count<=30;count++) " why do you use count here?

would you please tell why? -_-!!!

my binary search code:

int judge(double t){

double now = -1500000000;

for(int i=1;i<=n;i++){

if(node[i].type==1){

double test = node[i].x + node[i].v * t;

if(test > now) now = test;

}

else{

double test = node[i].x - node[i].v*t;

if(test<=now+epx) return 1;

}

}

return 0;

}

// in main function

double left = 1e-10, right = (node[n].x - node[1].x)/2.0 + 1;

while(aabs(left-right)>epx){

double mid = (left + right)/2;

if(judge(mid)==1) right = mid;

else left = mid;

}

what should be the output for this test case for problem A ? ~~~~~ 5

`1 2 1`

`5 4 4`

`2 3 2`

`3 4 3`

`5 1 5`

Congrats egor !!!

I'v just found new solution for problem E and my code AC 2676662. We could use binary search on distance between two successive colliders that their sign of speed changes from positive to negative.Use this we could figure out the places that colliders could make a Big Bang. By dividing the speed of each collider into the distance from places that we calculate before , we could found the answer. another thing that this problem has very bad exact time limit so we must use printf. and sorry for my bad english :D