Codeforces #399 D: Jon and Orbs

p[i]<=1000に注目する。
p[i]/2000 <= 1000/2000 = 1/2　(1)

i = 0,1,2,...,T
ターンたったときに全種類そろっている確率をf[i]とし、これをすべて求めて
l[i] = (p[i]-ε)/2000 の値で二分探索すればいい。
ただし、(1)よりf[T]>=1/2でなければならない。
そのようなTはk<=1000とkの値がそれほど大きくないので、じつはあまり大きくない。
つまり、1000種類のオーブが揃う確率を1/2以上にしたい場合、極端に多くのターンは必要なさそう。
ちなみに
T<=10000
これは十分に直感的だが、f[i]を実際に求めるだけで確かめられるし、そうすれば解も計算できる。
f[i]の求め方
g[i][j] := iターンたったとき、j種類揃っている確率
のDPを解けばいい。オーブを区別しなくていいことが重要。

実行時間
O(Tk + qlg(T))

思いつき方

入力の制約から気づく