### **1. Clothes (A Div-2)**

### **2. Sum of digits (B Div-2)**

### **3. Homework (C Div-2, A Div-1)**

*x*letter and lose them. Obvious thet if he lose

*x*rarest letters then overall number of losed letter do not increase, and then if he can lose some

*x*lettes, he can lose

*x*rarest ones. Thus it's easy to determine if Gerald can loses

*x*letters. And now to calculate the answer one only need to find the minimal such

*x*, so Gerald can lose

*x*letters.

### **4. Buses (D Div-2, B Div-1)**

*n*lets calculate

*k*

_{ x}- number of ways come to them. Consider the

*i*-th bus. Number of ways come to stop

*t*

_{ i}applied

*i*-th bus is uqual to number of way to embus to

*i*-th bus.

*i*-th bus on the stops

*s*

_{ i},

*s*

_{ i}+ 1, ...,

*t*

_{ i}- 1. Thus number of ways come to stop

*t*

_{ i}in the

*i*bus is equal to sum

*k*

_{ s i}+

*k*

_{ s i + 1}+ ... +

*k*

_{ t i - 1}. Finally, lets note that overall number of way to come to stop

*t*

_{ i}is the sum of numbers of ways to come to stop

*t*

_{ i}on every bus.

*n*≤ 10

^{9}. Therefore all

*k*

_{ x}not climb in memory limit. But we need to know only non-zero

*k*

_{ x}. For instance, one can gripe coordinates: create list of all occured stops (and also stops 0 and

*n*), sort this list, delete the repeated stops and replace all numbers of stops they indexes in this list. After this operations all number of stops not exceed 200001, and all

*k*

_{ x}are climb to the memory.

*k*

_{ s i}+

*k*

_{ s i + 1}+ ... +

*k*

_{ t i - 1}, asymptotic of time of working will be O(m^2). There is an easy way to solve this problem: one can create and update array

*sum*[], such that

*sum*[

*i*] =

*k*[0] +

*k*[1] + ... +

*k*[

*i*- 1], by another words,

*sum*[0] = 0,

*sum*[

*i*+ 1] =

*sum*[

*i*] +

*k*[

*i*].

*t*

_{ i}using bus

*i*is equal to

*sum*[

*t*

_{ i}] -

*sum*[

*s*

_{ i}].

### **5. Vectors (E Div-2, C Div-1)**

*a*=

*x*

_{ A}+

*iy*

_{ A},

*b*=

*x*

_{ B}+

*iy*

_{ B}and

*c*=

*x*

_{ C}+

*iy*

_{ C}. One can do operation

*A*→

*A*+

*C*and

*A*→

*iA*.

*A*, we will get number

*A*·

*i*

^{ k}+

*aC*+

*biC*-

*cC*-

*idC*for some non-negative integers

*k*,

*a*,

*b*,

*c*,

*d*or, in another words,

*A*·

*i*

^{ k}+

*aC*+

*biC*for

*k*= 0, 1, 2, 3 and some integers

*a*,

*b*. Since

*k*can be equal only 0, 1, 2 or 3, sufficiently to get to know is one can to represent

*B*-

*A*,

*B*-

*iA*,

*B*+

*A*or

*B*+

*iA*in the form of

*aC*+

*biC*.

*D*=

*aC*+

*biC*in the form of linear real equation system:

*a*·

*x*

_{ C}-

*b*·

*y*

_{ C}=

*x*

_{ D}

*a*·

*y*

_{ C}+

*b*·

*x*

_{ C}=

*y*

_{ D}

**6. Castle (D Div-1)**

*x*. Then he must to travel throw hole subtree, otherwise he will not visit all vertex in subtree. Then he come back to 0 and go to some next its child.

*n*children. Lets

*i*-th subtree have

*k*

_{ i}offspring (inclusive

*i*-th child of 0).

*N*vertexes.

*T*

_{ i}is the doubled sum of lenght all edges in

*i*-th subtree, inclusive edge between 0 and its

*i*-th child. It is the time to travel throw hole

*i*-th subtree, starting in 0 and returning to 0.

*t*

_{ i}is answer to problem on

*i*-th subtree. At once we add to this time length of edge between 0 and its

*i*-th child.

*n*. What is average time of finding the treasure?

*t*

_{1}.

*T*

_{1}+

*t*

_{2}.

*i*and

*i*+ 1 subtrees. Then item

*k*

_{ i + 1}

*T*

_{ i}disappear from sum and appear item

*k*

_{ iT}

_{ i + 1}. Sum will chenge to

*k*

_{ iT}

_{ i + 1}-

*k*

_{ i + 1}

*T*

_{ i}. Sum will decrease, if

*k*

_{ iT}

_{ i + 1}-

*k*

_{ i + 1}

*T*

_{ i}< 0, in ather words .

**7. Candies and Stones. (E Div-1)**

*n*×

*m*in cell of wich placed numbers. And one must go from cell (0, 0) to cell (

*n*- 1,

*m*- 1), doing moves to one cell up and right (that is, increasing by 1 on of coordinates), maximizing sum o number on the cell in the path.

*m*+

*n*- 1 cells of optimal path. Lets start with search one, middle cell. Lets . What cell of board can be

*k*-th in path? It is cell, sum of coordinate of wich is equal to

*k*, thus, it is diagonal of doard. And then we can calculate, what maximum sum Gerald can collect, came to every cell in the diagonal, by dynamic programming in lower triangle. And the same way, we can calculate, what maximum sum Gerald can collect, came to cell (n-1,m-1), starting from every cell in the diagonal. Sumed up this to values, we calculate, what maximum sum Gerald can collect, came to from cell (0, 0) to cell (

*n*- 1,

*m*- 1), travel throw every cell in the diagonal. And now we will find cell (

*x*,

*y*), in wich maximum is reached. It is

*k*-th cell of the path. We used time

*O*((

*n*+

*m*)

^{2}) and memory

*O*(

*n*+

*m*).

*x*,

*y*) and from cell (

*x*,

*y*) to cell (

*n*,

*m*).

*n*+

*m*is

*r*.

*k*. Twice we are find middle cell of path of length . Four times we are find middle cell of path of length . And so on. Therefore, time of program working will be . Thus, this solution take time

*O*((

*n*+

*m*)

^{2}).