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 jth room, than a probability of such event consists of factors: Cci --- which students will go to jth room.
(1 / j)c· ((j - 1) / j)i - c --- probability, that c students will go to jth 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· Cci· 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.
When considering room j with c students inside it, the largest queue in this room is (c + basin[j] - 1) / basin[j]. Then mx is actually the greater of this value and k (hence the 'update').