关于本题，目前我只会 $\mathcal{O}(\text{Ans})$ 的算法，但是如果你不幸出生于风井省，你就会知道在风井省选中，往往，“数据有一定梯度”。
先特判 $p\ge q,p\le 0.5,q=1$ 的特殊情况。
当有 $2n+1$ 个预言家时，预言正确人数的生成函数为 $f_n=(1-p+px)^{2n+1}$，成功的概率为 $P_n=1-\sum\limits_{i=0}^{n}[x^i]f_n$，求导并比较系数可得 $P_n=P(n-1)+\dbinom{2n-1}{n}p^n(1-p)^n(2p-1)$，故从小到大枚举 $n$ 即可并在 $P_n\ge q$ 时跳出循环即可。
。