**A. Bender Problem**

Solution by Polichka

Let's look at the first nail. If it is occupied by the fold place, then Bender will put next fold place on the third nail, then on fifth and so on. Else, is the first nail occupied by end, than second, fourth, sixth and so on nail will be occupied by the fold places.

Let's see, if we can complete our polyline with the first nail, occupied by rhe fold place. It means we should check, if we have an unused pod with length *dist*(*nails*[*n*], *nails*[1]) + *dist*(*nails*[1], *nails*[2]). Then check the third nail and so on.

If we have completed the polyline, then we have an answer. Else repeat previous procedure, but starting from the second nail.

**B. pSort**

Solution by Polichka

Let's consider a graph. Vertexes will correspond to place of the permutation. Places will be connected by an edge if and only if we can swap theirs values. Our problem has a solution when for every i, vertex p[i] can be reached from vertex i.

**C. Bath Queue**

Solution by Fefer

This problem is solved by dynamic programming

Consider the following dynamics: *d*[*i*][*j*][*k*].

*i* --- number of not yet processed students,

*j* --- number of not yet processed rooms,

*k* --- maximum queue in the previous rooms.

The value we need is in state *d*[*n*][*m*][0]. Let's conside some state (*i*, *j*, *k*) and search through all *c* from 0 to *i*. If *c* students will go to *j*th room, than a probability of such event consists of factors: *C*^{c}_{i} --- which students will go to *j*th room.

(1 / *j*)^{c}· ((*j* - 1) / *j*)^{i - c} --- probability, that *c* students will go to *j*th room,and the rest of them will go to the rooms from first to *j* - 1th.

Sum for all *ñ* from 0 to *i* values of

(1 / *j*)^{c}· ((*j* - 1) / *j*)^{i - c}· *C*^{c}_{i}· *d*[*i* - *c*][*j* - 1][*mx*]. Do not forget to update maximum queue value and get the accepted.

**D. Do not fear, DravDe is kind**

Solution by RAD

Let's split all trucks into different classes by the sum of *l*_{i} + *c*_{i} + *r*_{i}. Answer sequence consists of trucks from only one class, so let's solve problem for different classes independently.

Let's loop through trucks from fixed class in the order, then follow in the motorcade and update values in dynamics *z*[*k*] - maximum profit we can get, if last truck has *r*_{i} = *k*.

Truck with number i can update two values:

it can update value *z*[*r*_{i}] with value *z*[*r*_{i} + *c*_{i}] + *v*_{i}. It means this truck continued some motorcade, started from some previous truck.

if *l*_{i} = 0 it can update value *z*[*r*_{i}] with *v*_{i}. It means this truck started motorcade. Answer will be in *z*[0]

To restore the trucks included in the answer, we can keep with the maximal sum in z the index of last truck that updated this sum. Also we store the ancestor p for each truck that updated something in z. This ancestor is calculated when we consider i-th truck and doesn't change further: p[i] = -1 if truck i became beginning of the motorcade, otherwise p[i] = last truck that updated *z*[*r*_{i} + *c*_{i}]. We start restore of the answer from last truck updated z[0]. After that we restore everything using only p.

**E. DravDe saves the world**

Solution by Gerald

Problem by RAD

Let's look at geometrical locus where DravDe can land. It can be eigher an angle or a line(half-line).

1. Locus is an angle if and only if projection of vector *v* and vector *u* on Oxy plane is not collinear. This angle is easy to calculate. Angular vertex is DravDe starting point and one of half-lines is collinear with place speed vector projection. Second half-line is easy to calculate:

*A*_{z} + *V*_{z}· *tv* + *U*_{z}· *tu* = 0

*A*_{x} + *V*_{x}· *tv* + *U*_{x}· *tu* = *B*_{x}

*A*_{y} + *V*_{y}· *tv* + *U*_{y}· *tu* = *B*_{y}

where A - starting point, B - landing point. Consider tv equal to 1 and calculate tu from first equation. From second and third calculate point B. This point lies on the second half-line of the angle.

2. If plane speed projection and wind speed projection is collinear, locus is half-line or line, depending on the difference between this two speeds.

If the answer exist, than polygon and locus have at least onecommon point. And t1 and t2 is minimal on edge points. So now let's cross all segments with locus, calculate t1 and t2 for each intersection point and select minimal answer. Thank you for your participation. Good luck with upsolving and incoming contests. Luck - is very useful and it is good to have it.

With best regards, Ivan.

C^{c}_{i}evaluate to?--- which students will go to

jth roomdoes it mean c students are selected from the maximum number of students i, where c can vary from 0 to i.

i! / ( c! * (i-c)! )

Also, I think maximum number of students i is the same as the maximum number of students in the input that is "n".

mx - is the maximum queue in previous rooms.

No. i - is different. When we select some c students for jth room, for (j-1)th room there will be only (i - c) students left.

what is the test 9 of Problem D?

Oh... I can't stand the decription of the problems any more. I have to read 5 times to understand.