For the first time, our team will write tutorials separetly, but we will unite the in one post after everything will be ready.

**C. Bath Queue**

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.

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.

kismaximum queue length so far. Of course, when there are m not processed rooms (i.e. all rooms haven't been processed), maximum queue is 0 (no queue yet).When considering room

jwithcstudents inside it, the largest queue in this room is(. Thenc+ basin[j] - 1) / basin[j]mxis actually the greater of this value andk(hence the 'update').